Given a particular value x and an array A, I'd like some way to determine (without literally checking each possible combination) all of the combinations of numbers in A that sum to it.

Thanks to Jeff Erickson's wonderful algorithm notes, I can write an algorithm that efficiently determines if a sum exists, but I'm having trouble modifying it to actually remember the numbers it uses. The memoized version in the aforementioned notes doesn't seem to admit any way to keep track of anything, particularly because the number of distinct combinations of numbers may well be greater than $x*len(A)$.

If it helps, for my particular purpose, I'm assuming the numbers in my array are monotonically increasing (notably, no repeats.)

Also if the algorithm could be some polynomial combination of the input size and the value we're summing to, and not exponential, that'd be amazing. I plan to run this subroutine many many times, hahaha.

  • $\begingroup$ This is a version of subset sum problem which is a known NP-Complete problem. So polynomial algorithm is not designed yet. But if you want the index/numbers from array then you have to store the value in a vector and need to pass that in each recursive call. For implementation you can refer answer given in stackoverflow.com/questions/4632322/… $\endgroup$ – Pragya Nov 24 '17 at 10:47
  • $\begingroup$ There could be infinitely many such combinations. For example, suppose that the array $A$ contains $n$ many copies of 1, and that $x = n/2$. $\endgroup$ – Yuval Filmus Nov 24 '17 at 12:31
  • $\begingroup$ @YuvalFilmus $\binom{n}{n/2}$? $\endgroup$ – Ariel Nov 24 '17 at 12:43
  • 1
    $\begingroup$ @Ariel Right, which is exponential in $n$. I meant to write exponential rather than infinite... $\endgroup$ – Yuval Filmus Nov 24 '17 at 13:02
  • $\begingroup$ Thanks, @Pragya! That answers my question, even if I'm going to grumble a little bit about it being NP. $\endgroup$ – Willbeing Nov 24 '17 at 19:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.