查找与特定值相加的所有子集

Question

这类似于子集和问题，只是稍有不同，不是检查集合是否有一个和为9的子集，而是我们必须找到这样的子集的个数。我在这里遵循子集和问题的解法。但是我想知道如何修改它来返回子集的计数。

Answer 1

def total_subsets_matching_sum(numbers, sum):
    array = [1] + [0] * (sum)
    for current_number in numbers:
        for num in xrange(sum - current_number, -1, -1):
            if array[num]:
                array[num + current_number] += array[num]
    return array[sum]

assert(total_subsets_matching_sum(range(1, 10), 9)       == 8)
assert(total_subsets_matching_sum({1, 3, 2, 5, 4, 9}, 9) == 4)

解释

这是经典问题之一。其思想是找到与当前数可能的和的个数。这是真的，有一种方法使和为0。刚开始的时候，我们只有一个号码。我们从我们的目标（解决方案中的变量最大值）开始，然后减去这个数字。如果有可能得到该数字的和（对应于该数字的数组元素不是零），则将其添加到对应于当前数字的数组元素中。这样程序就更容易理解了

for current_number in numbers:
    for num in xrange(sum, current_number - 1, -1):
        if array[num - current_number]:
            array[num] += array[num - current_number]

当数字为1时，只有一种方法，你可以得出1的和（1-1变成0，对应0的元素是1）。所以数组将是这样的（记住元素零将有1）

[1, 1, 0, 0, 0, 0, 0, 0, 0, 0]

[1, 1, 1, 1, 0, 0, 0, 0, 0, 0]

[1, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 1, 1, 1, 0, 0, 0, 0, 0, 0]
[1, 1, 1, 2, 1, 1, 1, 0, 0, 0]
[1, 1, 1, 2, 2, 2, 2, 2, 1, 1]
[1, 1, 1, 2, 2, 3, 3, 3, 3, 3]
[1, 1, 1, 2, 2, 3, 4, 4, 4, 5]
[1, 1, 1, 2, 2, 3, 4, 5, 5, 6]
[1, 1, 1, 2, 2, 3, 4, 5, 6, 7]
[1, 1, 1, 2, 2, 3, 4, 5, 6, 8]