# Subset Sum: reduce special to general case

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?

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.

• Thank you very much. I wonder, is there a reduction which transforms an instance of 0-subset-sum to one (instead of $n$) instance of K-subset-sum? – ipsec Apr 3 '13 at 16:34
• @ipsec: You mean transform an instance of K-subset-sum to 0-subset-sum? Perhaps taking the union of the $n$ sets above will work. – Aryabhata Apr 3 '13 at 17:31
• Well, I was actually thinking twice whether I got the rigth direction now. When I want to show that K-subset-sum is NP-hard for every K given the fact, that 0-subset-sum is NP-hard, I can use a reduction from 0-subset-sum to K-subset-sum, for which I would need a poly-time transformation from any 0-instance to a K-instance. But I am not certain now that this is actually what I have asked in my question. – ipsec Apr 3 '13 at 19:19
• @ipsec: When you say set $s=0$, you have show the NP-Hardness of $K$-subset-sum given the NP-Hardness of zero-subset-sum: the general problem is at least as hard as the special problem. Note that in reduction terms, you say you have reduced zero-subset-sum to $K$-subset-sum. Also, note that $K$ is an input. When you talk about "every given $K$" what exactly do you mean? The above answer shows that the special case(zero-subset-sum) is as hard (in NP-hardness sense) as the general case ($k$-subset-sum, where $k$ is an input). – Aryabhata Apr 4 '13 at 4:40
• Never mind. What I originally was wondering about is, if we know that 0-subset-sum is NP-hard, can we derive, that e.g. 1-subset-sum is as well? Wikipedia says so, but I was looking for a proper reduction. However I see now that my wording was totally messed up and I was in fact asking the opposite. Anyway you gave me enough input to reduce from any K-subset-sum instance to a L-subset-sum instance for any given integers K and L, so my problem is still solved. – ipsec Apr 4 '13 at 15:08