Search code examples
algorithmsetcombinationsheuristicsnp-complete

Find set of numbers in one collection that adds up to a number in another

For a game I'm making I have a situation where I have a list of numbers – say [7, 4, 9, 1, 15, 2] (named A for this) – and another list of numbers – say [11, 18, 14, 8, 3] (named B) – provided to me. The goal is to find all combinations of numbers in A that add up to a number in B. For example:

  • 1 + 2 = 3
  • 1 + 7 = 8
  • 2 + 9 = 11
  • 4 + 7 = 11
  • 1 + 2 + 4 + 7 = 14
  • 1 + 2 + 15 = 18
  • 2 + 7 + 9 = 18

...and so on. (For purposes of this, 1 + 2 is the same as 2 + 1.)

For small lists like this, it's trivial to just brute-force the combinations, but I'm facing the possibility of seeing thousands to tens of thousands of these numbers and will be using this routine repeatedly over the lifespan of the application. Is there any kind of elegant algorithm available to accomplish this in reasonable time with 100% coverage? Failing this, is there any kind of decent heuristics I can find that can give me a "good enough" set of combinations in a reasonable amount of time?

I'm looking for an algorithm in pseudo-code or in any decently popular and readable language (note the "and" there....;) or even just an English description of how one would go about implementing this kind of search.

Edited to add:

Lots of good information provided so far. Thanks guy! Summarizing for now:

  • The problem is NP-Complete so there is no way short of brute force to get 100% accuracy in reasonable time.
  • The problem can be viewed as a variant of either the subset sum or knapsack problems. There are well-known heuristics for both which may be adaptable to this problem.

Keep the ideas coming! And thanks again!

Solution

  • This problem is NP-Complete... This is some variation of the sub-set sum problem which is known to be NP-Complete (actually, the sub-set sum problem is easier than yours).

    Read here for more information: http://en.wikipedia.org/wiki/Subset_sum_problem