in reply to Re: Find combination of numbers whose sum equals X
in thread Find combination of numbers whose sum equals X
Well ... almost.
The Subset Sum Problem asks if there is one solution.
But the OP asks to "list all possible combination of numbers"
Algorithm wise that's a huge difference, because one can often optimize searching for a single solution, while happily ignoring the rest. °
And that's also why I'm hesitant solving this, you can easily show that the solution space of all possible combinations will explode quickly, in a way that already the time needed to print them out will take an eternity.
I.O.W. such problems don't make much sense, unless you are singling out a single (or a few) solution which are optimal regarding a second value-function.
Cheers Rolf
(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery
°)The Knapsack Problem will also demand to optimize a second "value" function and only require the "weight" to be less or equal the "target". It's a generalization of Subset Sum b/c if you choose the weight as value, the equal case - if it exists - will be maximal.