Why does basic Subset Sum algorithm not handle negative values?

Question

In class we went over a solution for the subset sum problem (given a set S of positive numbers, does a subset of S exist that sums to a positive value T). Here is my python implementation of the algorithm with a simple test case:

def ss(s, i, t):
    if t == 0:
        return True
    if i == (len(s)-1):
        return s[i] == t
    return ss(s, i+1, t-s[i]) or ss(s, i+1, t)

s = [1, 3, 5]
t = 8 
print(ss(s, 0, t))
>> True

We are supposed to make and prove correctness for a modified algorithm that can handle negative values in S and for T. However, it seems like every set with negative values I have tried so far on the unmodified algorithm still works. I can't seem to find an example where this algorithm fails for negative values.

Could someone explain to me why this algorithm doesn't work for all negative values and possibly give a counter example to demonstrate this?

This does not look like a dynamic programming implementation of the subset sum problem, but more a recursive "brute force" approach. — Willem Van Onsem
This works for negative numbers. It's possible that the purpose of the assignment was for you to realize and prove that it works, or that you got the original algorithm wrong, or that you misunderstood the assignment. — user2357112 supports Monica
Ok, I'm thinking I must have misunderstood the notes I took from class and implemented the wrong approach. But I'm glad to know that this approach does work for negative numbers because I couldn't figure out why I couldn't get it to fail. — greyer

Unknown Unknown · Accepted Answer · 2019-02-16T22:18:27

This indeed works for negative numbers. Perhaps, as was mentioned, the idea is to prove the correctness of the algorithm with different pre-conditions and post-conditions? depending on how you are proving the correctness of it.

Note that this works in Python because there is not an explicit "natural numbers" restriction in the language. If you are using pseudo-code or more restrictive programming languages, these restrictions would make more sense. Hope it helps.

Why does basic Subset Sum algorithm not handle negative values?

1 Answers