查找所有总和为特定值的子集

Question

给定一组数字：{1、3、2、5、4、9}，找到合计为特定值的子集数量（例如，本示例为9）。

这类似于子集总和问题，只是存在细微差异，而不是检查集合是否有一个总和为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]现在，第二个数字为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。

Answer 2

您可以使用动态编程。算法复杂度为O（Sum * N），并使用O（Sum）内存。这是我在C＃中的实现：private static int GetmNumberOfSubsets(int[] numbers, int sum){&nbsp; &nbsp; int[] dp = new int[sum + 1];&nbsp; &nbsp; dp[0] = 1;&nbsp; &nbsp; int currentSum =0;&nbsp; &nbsp; for (int i = 0; i < numbers.Length; i++)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; currentSum += numbers[i];&nbsp; &nbsp; &nbsp; &nbsp; for (int j = Math.Min(sum, currentSum); j >= numbers[i]; j--)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; dp[j] += dp[j - numbers[i]];&nbsp; &nbsp; }&nbsp; &nbsp; return dp[sum];}注意：由于子集数可能具有2 ^ N的值，因此很容易会溢出int类型。算法仅适用于正数。