Problem Detail: Wikipedia states the subset sum problem as finding a subset of a given set of integers, whose sum is zero. Further it describes it as equivalent to finding a subset with sum $s$ for any given $s$. So I believe as they are equivalent, there must be a reduction in either side. The one from $s$ to zero is trivial by setting $s = 0$. But I had no luck finding a reduction from zero to $s$, i.e. given a set of integers $A$, construct a set of integers $B$ containing a subset with sum $s$ (for any $s$), if and only if there is as subset of $A$ with sum zero. Can you give me some pointers?
Asked By : ipsec
Answered By : Aryabhata
You actually already have a reduction from special to general. By setting $s=0$, you are basically using the general algorithm to solve the special problem. For the other way round (i.e. a reduction from general to special): Suppose you are given a set $S = {x_1, dots, x_n}$ and a number $K$ and you have to determine if there is some subset of $S$ which sums to $K$. Now you want to solve this problem, given an algorithm for the case where you can determine if some subset sums to $0$. Now if $x_i gt 0$, we have an easy reduction: $S’ = {x_1, x_2, dots, x_n, -K}$. $S’$ has a subset of sum $0$ iff $S$ has a subset of sum $K$. The problem occurs when we can have $x_i le 0$ for some of the $i$. We can assume that $K gt 0$ (why?). Suppose the sum of the positive $x_i$ is $P$ and the negative $x_i$ is $N$. Now construct a new set $S’ = {y_1, y_2 dots, y_n}$ such that $y_i = x_i + M$ where $M = P + |N| + K$. Each $y_i gt 0$. Now run the zero-subset-sum algorithm on the sets $ S’ cup {-(K+M)}$ $ S’ cup {-(K+2M)}$ $ S’ cup {-(K+3M)}$ $dots$ $ S’ cup {-(K+nM)}$ It is easy to show that if $S$ has a subset of sum $K$, then at least one of the above sets has subset of sum zero. I will leave the proof of the other direction to you.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/10981
