Looking for an algorithm

Question

I have a very long "list" of numbers ( maybe thousands ) which may be grouped, by sum into "n" groups. The number of groups and values are given. For example:

• List of numbers: [1, 2, 5, 6, 7, 8, 10]
• Groups:[3, 15, 21]

I need to find a summary of which numbers in the "list" will crate given "groups".

• 3 = 1+2
• 15 = 5+10
• 21 = 6+7+8

We may assume numbers are integers but may be negative. It looks like a subset sum problem, but one of the biggest constraints is matching ALL the numbers to ALL groups.

Ideas?

Answer 1

We can show that your problem is at least as hard as subset sum very easily.

Recall that subset sum is "Given a set of integer of S, is there a subset s of S that sum to T".

If we frame this as your problem we would want two groups T and sum(S)-T. If you could solve your problem with these two groups, we would also have a solution two the original subset sum problem. We see that an algorithm that solves your problem also would solve Subset Sum, but since Subset Sum is a NP-complete problem, we can also say that your problem is NP-hard. (This is known as a reduction from a NP-hard problem).

To show that the problem is NP-complete we have to also show that problem is in NP. A problem in NP is any decision problem where a solution can be verified in polynomial time. Given any proposed solution to your problem, it is trivial to verify if the sum in each group is what we want it to be. So the problem is also in NP.

As such there is (probably) no polynomial time algorithm solving your problem. There might be pseudo-polynomial algorithms such as Knapsack that could work, but since you state your problem size is in the thousands there is no hope these will be fast enough.