为什么基本的子集和算法不能处理负值？

Question

在课堂上，我们讨论了子集和问题的解决方案（给定S的正数，S的子集是否存在，它总和为正值T）。这是我的算法的python实现，带有一个简单的测试用例：

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

我们应该为修改后的算法制定并证明其正确性，该算法可以处理S和T中的负值。但是，似乎每个具有负值的集合我到目前为止在未修改的算法上仍然可以工作。我似乎找不到这个算法因负值而失败的例子。

有人可以向我解释为什么这个算法不适用于所有负值，并可能给出一个反例来证明这一点吗？

Answer 1

这确实适用于负数。或许，如前所述，这个想法是用不同的前置条件和后置条件来证明算法的正确性？取决于你如何证明它的正确性。

请注意，这在Python中有效，因为语言中没有明确的“自然数”限制。如果您使用伪代码或更严格的编程语言，这些限制将更有意义。希望能帮助到你。