I'm trying to proof that a problem of subset from a group has a sum of zero.
I know that i can use the partition problem that is known to be NP-complete, but i can't seems to find what i need to change in the group so it will give the sum of zero.
Thank you.
Best Answer
So you want to reduce the partition problem to the subset sum problem.
Hint: Given an instance of the partition problem, sum the numbers and halve the sum to find out what each side of an equal partition must sum to. Append minus this number to the problem, and feed the resulting multiset to the hypothesized subset-sum solver.