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.