给定一组数字:{1、3、2、5、4、9},找到合计为特定值的子集数量(例如,本示例为9)。
这类似于子集总和问题,只是存在细微差异,而不是检查集合是否具有总和为9的子集,我们必须找到此类子集的数量。我在这里关注子集和问题的解决方案 。但是,我想知道如何修改它以返回子集的计数。
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。