algorithm - 找到总和为特定值的所有子集

Question

给定一组数字:{1, 3, 2, 5, 4, 9}，找出总和为特定值(例如，本例为 9)的子集数。

这类似于子集求和问题，但略有不同的是，我们不必检查集合是否有总和为 9 的子集，而是必须找出此类子集的数量。我正在关注子集和问题的解决方案 here .但是我想知道如何修改它以返回子集的计数。

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]

现在，第二个数字是 2。我们开始从 9 中减去 2，它无效(因为 7 的数组元素为零，我们跳过它)我们一直这样做直到 3。当它的 3、3 - 2 为 1 并且1对应的数组元素为1，我们将其添加到3的数组元素。当它的2, 2 - 2变为0时，我们将0对应的值添加到2的数组元素。经过此迭代，数组如下所示

[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]

在最后一次迭代之后，我们会考虑所有的数字，得到目标的方法数就是目标值对应的数组元素。在我们的例子中，最后一次迭代后的 Array[9] 是 8。