What is the best algorithm for this?

We are given an array of positive integers and we want to minimize the total cost of recursively adding together all the integers to one integer, two integers at a time. The cost of each addition is the sum of the two integers, and this sum adds up cumulatively. After each addition, the two integers are removed from the array, but their sum is added, until only one value remains.

I think I have figured out so far that the optimal solution is to add up the two smallest values in the array at every step (as the earlier the figure is used the more times it is included in the cumulative cost.) Perhaps there is another way to think about the problem, though.

Is there some mathematical fact that trivializes the solution perhaps?

Example A:

Input: [1, 5, 3, 7]
Adding 1 and 3 together (Cost 1+3 = 4)
State: [5, 7, 4]
Adding 4 and 5 together (Cost 4+5 = 9)
State: [7, 9]
Adding 7 and 9 together (Cost 7+9 = 16)
State: [16]

Total cost: 4 + 9 + 16 = 29

Example B:

Input: [1, 1, 1, 1, 1]
Adding 1 and 1 together (Cost 1+1 = 2)
State: [1, 1, 1, 2]
Adding 1 and 1 together (Cost 1+1 = 2)
State: [1, 2, 2]
Adding 1 and 2 together (Cost 1+2 = 3)
State: [2, 3]
Adding 2 and 3 together (Cost 2+3 = 5)
State: [5]
Total cost: 2 + 2 + 3 + 5 = 12

(I made these examples up myself; let me know if the examples are not actually the optimal solutions, although I am pretty confident they are.)

  • $\begingroup$ (Sounds Huffman rather than subset sum.) $\endgroup$
    – greybeard
    Commented Dec 5, 2018 at 6:17
  • $\begingroup$ @graybeard Thanks, I removed it. I was trying to look for something fitting containing "sum"... $\endgroup$
    – MakaPeia
    Commented Dec 5, 2018 at 18:05

1 Answer 1


This problem can be solved using a min heap. You have to construct a min heap initially with all the elements of array. Now you simply take the top element of this heap and add it to the next top element of heap. Then reinsert the sum obtained in the heap. Keep a variable to track the total cost. This will ensure that you are adding the minimum elements and the final cost is minimum. This is analogous to the problem of connecting n ropes with minimum cost.

  • $\begingroup$ Wow! Thanks friend! I felt there would be a "simple" solution... The min heap algorithm is exactly what it needs. $\endgroup$
    – MakaPeia
    Commented Dec 5, 2018 at 18:04
  • $\begingroup$ I once tried this problem and came up with an algorithm which sorted the array and then kept on doing sum but that was incorrect. It missed some cases and min heap algorithm was the correct one. Reading your case it took me just a second to recognise the problem ;) $\endgroup$ Commented Dec 6, 2018 at 22:55
  • 1
    $\begingroup$ Why this solution is correct is asked in this post. $\endgroup$
    – xskxzr
    Commented Aug 22, 2019 at 7:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.