找到总和为特定值的所有子集 [英] find all subsets that sum to a particular value

问题描述

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

Given a set of numbers: {1, 3, 2, 5, 4, 9}, find the number of subsets that sum to a particular value (say, 9 for this example).

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

This is similar to subset sum problem with the slight difference that instead of checking if the set has a subset that sums to 9, we have to find the number of such subsets. I am following the solution for subset sum problem here. But and I am wondering how I can modify it to return the count of subsets.

推荐答案

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)

说明

这是经典问题之一.这个想法是用当前数字找到可能和的数量.确实，只有一种方法可以将 sum 变为 0.一开始，我们只有一个数字.我们从我们的目标(解决方案中的变量最大值)开始并减去该数字.如果可以得到该数字的总和(该数字对应的数组元素不为零)，则将其添加到当前数字对应的数组元素中.这样程序会更容易理解

This is one of the classic problems. The idea is to find the number of possible sums with the current number. And its true that, there is exactly one way to bring sum to 0. At the beginning, we have only one number. We start from our target (variable Maximum in the solution) and subtract that number. If it is possible to get a sum of that number (array element corresponding to that number is not zero) then add it to the array element corresponding to the current number. The program would be easier to understand this way

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)

When the number is 1, there is only one way in which you can come up with the sum of 1 (1-1 becomes 0 and the element corresponding to 0 is 1). So the array would be like this (remember element zero will have 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的数组元素中.经过这次迭代，数组看起来像这样

Now, the second number is 2. We start subtracting 2 from 9 and its not valid (since array element of 7 is zero we skip that) we keep doing this till 3. When its 3, 3 - 2 is 1 and the array element corresponding to 1 is 1 and we add it to the array element of 3. and when its 2, 2 - 2 becomes 0 and we the value corresponding to 0 to array element of 2. After this iteration the array looks like this

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

我们一直这样做，直到我们在每次迭代后处理所有数字和数组看起来像这样

We keep doing this till we process all the numbers and the array after every iteration looks like this

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

After the last iteration, we would have considered all the numbers and the number of ways to get the target would be the array element corresponding to the target value. In our case, Array[9] after the last iteration is 8.

这篇关于找到总和为特定值的所有子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！