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?

Improve this question
$\endgroup$
1
  • $\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
    Commented Oct 26, 2012 at 6:41

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
6
  • 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
    Commented Oct 26, 2012 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
    Commented Oct 26, 2012 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
    Commented Oct 26, 2012 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
    Commented Oct 26, 2012 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
    Commented Dec 9, 2016 at 23:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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