Interview q: Small possible length of stick from an array of stick lengths I was asked this question in a phone interview recently and I bombed it completely. Zero clue how to approach it. I wasn't able to find any similar patterns on google-ing. Thought maybe folks here might be able to help?

Statement: Given m sticks with different lengths. Combine these sticks to form longer sticks with the same length. What’s the smallest possible length of these newly unified sticks?
Conditions:

Must use all sticks
m &lt; 50
max length of single stick less than 20

Example:
Input: 5 2 1 5 2 1 5 2 1
Output: 6
(Process: 1+5, 1+5, 1+5, 2+2+2)


Input: 3 3 3 2 2 5
Output: 9
(Process: 3+3+3, 2+2+5)


Input: 1 2 3 4 5
Output: 5
(Process: 2+3, 1+4, 5)


Input: 1 3 4 5
Output: 13
(Process: 1+3+4+5)
Pragmatic approach: If I were given this in an interview, I'd formulate it as an integer linear programming problem and let an off-the-shelf ILP solver look for a solution for me.
Theoretical approach: As Dmitry mentions, this problem is related to bin packing.  (It's not identical because you require the bins to be full, whereas normal bin packing doesn't require that.)  Wikipedia says that there is a pseudopolynomial time algorithm for bin packing when the bin size is fixed, so you might look up that algorithm and see if it can be modified to apply to your problem.  You might also explore this paper:
Michel X. Goemans, Thomas Rothvoß. &quot;Polynomiality for bin packing with a constant number of item types&quot;. SODA 2014.