2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Merbs Oct 26 '12 at 6:41
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ the solution to the original problem was {-3, -2, 5} after shifting by 8 we get {5,6, 13}, this set doesnt add up to 40. $\endgroup$ – Mike G Oct 26 '12 at 2:57
  • $\begingroup$ but why has the original solution changed? I was thinking of shifting all the elements solve it, then reverse the solution("un-shift") it, shouldn't the relative differences between numbers stay the same and thus produces the same solution as the original solution ? $\endgroup$ – Mike G Oct 26 '12 at 3:01
  • $\begingroup$ 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. $\endgroup$ – Juho Oct 26 '12 at 3:04
  • $\begingroup$ but this implies that we know the original solution, which we dont before solving the problem, so this doesnt generalize, i find it really weird, is there a way to eliminate all the negative numbers and solve the problem without this anomaly? $\endgroup$ – Mike G Oct 26 '12 at 3:08
  • $\begingroup$ @MikeG, did you get a resolution on this? I agree that this answer makes no sense whatsoever, but given the positive score I wonder. $\endgroup$ – Scrub Dec 9 '16 at 23:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.