Thread: Sub-sum problem (NP)

Hi,
I'm new here but after googling a whole day, I couldn't find another solution then to ask you guys on this forum about some help for my problem.
I believe it's more advanced type of sub-sum problems. More advanced because sub-summing is limited only to '+' operations, here I have both, the '+' and '-' operations.
Here's the problem itself:
---
A set of natural numbers is given. Generate all the subsets of this set joined by alternating + and - operators which
sum up to exactly S. .
I/O description. Input: enumeration of elements in the set, on one line, then sum on one line e.g.
1 3 5 7 2 6
0
Output: enumeration of elements resulting in the given sum, e.g.
1-3+2
1+3-6
5-7+2
1+5-6
...
---

I thought a possible solution would be the generation of a matrice(table) in wich I would start placing 1 or -1 or 0 for each cell. But I didn't succed at all.
I thought maybe someone already had to deal with such a problem, but on the web I cound't find it's solution...
Thank you in advance...

Originally Posted by stass

I thought a possible solution would be the generation of a matrice(table) in wich I would start placing 1 or -1 or 0 for each cell. But I didn't succed at all.

You would need to add in the condition that you must have either the same numbers of 1's and -1's, or one more 1 than -1 (since we'll always add before we subtract).

That will help cut down on the number of 1/0/-1 combinations you would have to check. I don't know of any reasonably efficient other method.

Thank you tabstop, at least I'm on the right way.
Regards.