发现，总结到一个特定值的所有子集 [英] find all subsets that sum to a particular value

问题描述

给定一组数字：{1,3，2，5，4,9}，发现亚群之和为一个特定的值（例如，9本实施例）的数

这是类似于子集和问题的细微差别，而不是检查是否设定有总结到9的一部分，我们必须找到这样的子集的数量。我下面的子集和问题这里的解决方案。但是，我想知道我怎么可以修改它返回亚群的数量。

解决方案

高清total_subsets_matching_sum（数字总和）：     阵列= [1] + [0] *（总和）     对于CURRENT_NUMBER的数字：         为NUM中的xrange（总和 - CURRENT_NUMBER，-1，-1）：             如果array [数字]：                 阵列[NUM + CURRENT_NUMBER] + =阵列[数字]     返回数组[总和] 断言（total_subsets_matching_sum（范围（1，10），9）== 8） 断言（total_subsets_matching_sum（{1，3,2，5,4，9}，9）== 4）

说明

这是经典的问题之一。这样做是为了找到可能的和与当前数的数量。而其真正的，恰好有把总和为0。刚开始的一种方式，我们只有一个号码。我们从我们的目标（变量最大的解决方案）开始并减去这个数字。如果有可能获得该数值的总和（对应于该号码的数组元素不为零），然后将它添加到对应于当前编号的数组元素。该方案会更容易理解这种方式

的CURRENT_NUMBER的数字：     为NUM中的xrange（总和，CURRENT_NUMBER - 1，-1）：         如果array [NUM - CURRENT_NUMBER]：             阵列[数字] + =阵列[NUM - CURRENT_NUMBER]

当的数目是1时，只有一个，可以在其中拿出1之和的方式（1-1变为0和对应于0的元素是1）。因此，阵列会是这样（请记住元素零将有1）

的 [1，1，0，0，0，0，0，0，0，0]
 

现在，第二个数字是2，我们开始从9及其不是有效的（因为7数组元素是零，我们跳过）减去2我们继续这样做，直到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]
 

在最后一次迭代，我们会考虑所有的数字和的方法来获得目标将对应于该目标值的数组编号。在我们的例子中，数组[9]最后一次迭代后为8。

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

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)

Explanation

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]

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]

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]

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屋！