找出给定数字的可能组合

Question

使用下面的代码找出给定数字的可能组合。 Finding all possible combinations of numbers to reach a given sum

但是，如果总体中存在负值，则此公式将不起作用。为了解决这个问题，是否可以进行任何修改

提前谢谢

---

def subset_sum(numbers, target, partial=[]):
    s = sum(partial)

    # check if the partial sum is equals to target
    if s == target:
        print("sum(%s)=%s" % (partial, target))
    if s >= target:
        return  # if we reach the number why bother to continue

    for i in range(len(numbers)):
        n = numbers[i]
        remaining = numbers[i + 1:]
        subset_sum(remaining, target, partial + [n])


if __name__ == "__main__":
    subset_sum([-17896,-4774,-1472,701,912,2848,3431,3966], -12284)

Answer 1

乍一看：第二个检查if s >= target: return仅在正输入情况下有效。当输入值为负值时，部分和可以大于目标值。只需禁用此检查

sum([-17896, -4774, -1472, 701, 912, 2848, 3431, 3966])=-12284