# Shifting subset sum solution by constant positive integer

While reading the Wikipedia article about the subset sum problem I came across this example: "is there a non-empty subset whose sum is zero? For example, given the set $\{ −7, −3, −2, 5, 8 \}$, the answer is yes because the subset $\{ −3, −2, 5 \}$ sums to zero".

I have noticed that if we shift all the values of the set by adding a 8 to all elements we get $\{ 1, 5, 6, 13, 16 \}$ and then add the constant to the desired solution $0 + 8$, so now the question becomes is there a subset that adds up to $8$, which is not possible. My question is why does shifting the set and the solution by a positive integer "break" the solution, isn't the mathematics sound from the previous operations?

• One half solution is adding some number $k=\lvert\min(x_i)\rvert+1$ and then checking for every subset $Y=\{y_1,...,y_m\}$ whether $\sum y_i=\lvert Y\rvert\times k=m\times k$. Though I'd conjecture that the reason that work is restricted to the subset sum problem for nonnegative numbers is because translating is nontrivial. – Merbs Oct 26 '12 at 6:41

Your error is that you add your constant to the left-hand side of the equality multiple times, and only once to the right side. For example, $1+1=2$ clearly holds. If you add $8$ to both sides of it, you get $1+1+8=10$ which also holds. Erroneously you might add it twice to the left hand side and get $9+9=10$, which does not hold.
In your case, $0$ should not become $8$, but instead $8 \cdot 5 = 40$. Now a solution exists again.
• Try to see it this way: you start with $-3-2+5=0$. Then you add $8$ three times to the equation. You get $5+6+13=8+8+8$, which again holds. – Juho Oct 26 '12 at 3:04