[Solved]: Shifting subset sum solution by constant positive integer

Problem Detail: 

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?

Asked By : Mike G

Answered By : Juho

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6319