How to find out which subtotal make up a sum?

Question

I need to find numbers in a list, which make up a specific total:

Sum: 500

Subtotals: 10 490 20 5 5

In the end I need: {10 490, 490 5 5}

How do you call this type of problem? Are there algorithms to solve it efficiently?

Answer 1

This is Knapsack problem and it is an NP-complete problem, i.e. there is no efficient algorithm known for it.

Answer 2

1. This is not a knapsack problem.
2. In the worst case, with N subtotals, there can be O(2^N) solutions, so any algorithm in worst-case will be no better than this (thus, the problem doesn't belong to NP class at all).

Let's assume there are no non-positive elements in the Subtotals array and any element is no greater than Sum. We can sort array of subtotals, then build array of tail sums, adding 0 to the end. In your example, it will look like:

Subtotals:   (490, 20, 10,  5, 5)  
PartialSums: (530, 40, 20, 10, 5, 0)

Now for any "remaining sum" S, position i, and "current list" L we have problem E(S, i, L):
E(0, i, L) = (print L).
E(S, i, L) | (PartialSums[i] < S) = (nothing).
E(S, i, L) = E(S, i+1, L), E(S-Subtotals[i], j, L||Subtotals[i]), where j is index of first element of Subtotals lesser than or equal to (S-Subtotals[i]) or i+1, whichever is greater.
Our problem is E(Sum, 0, {}).

Of course, there's a problem with duplicates (if there were another 490 number in your list, this algorithm would output 4 solutions). If that's not what you need, using array of pairs (value, multiplicity) may help.

P.S. You may also consider dynamic programming if size of the problem is small enough:

1. Start with set {0}. Create array of sets equal to array of subtotals in size.
2. For every subtotal create a new set from previous set by adding subtotal value. Remove all elements greater than Sum. Merge it with previous set (it will essentially be the set of all possible sums).

3. If in the final set doesn't have Sum, then there is no solution. Otherwise, you backtrack solution from Sum to 0, checking whether previous set contains [value] and [value-subtotal].
   Example:

   (10, 490, 20, 5, 5)

Sets:

(0)
(0, 10)
(0, 10, 490, 500)
(0, 10, 20, 30, 490, 500) (510, 520 - discarded)
(0, 5, 10, 15, 20, 25, 30, 35, 490, 495, 500)
(0, 5, 10, 15, 20, 25, 30, 35, 40, 490, 495, 500)

From last set: [500-5] in previous set, [495-5] in previous set, [490-20] not in previous set ([490] is), [490-490] is 0, resulting answer {5, 5, 490}.