python 获取长度为 X 的列表，其中所有值的总和为 Y

Question

我需要在最短的时间内找到所有总和等于X的列表组合。

此刻我有这个:

def deduceArrayFromSum(arr, expectedSum, depth, maxDepth, intervalEnd, intervalStart):
    if maxDepth<=maxOffset:
        if expectedSum>0:
            i = min(intervalEnd, asum)
            while i>=intervalStart:
                if expectedSum>=i and depth<maxOffset:
                    arr[depth] = i
                    deduceArrayFromSum(arr, expectedSum-i, depth+1, maxDepth, i, intervalStart)
                i=i-1
        elif asum==0:
            foundSum(arr)

对于找到的每个组合，它都会调用 foundSum()

我希望我可以通过使其线性而不是递归调用来优化它，并避免在每次调用时发送 arr 变量。另一种可能的加速方法是使用 yield ，但我似乎无法理解它是如何工作的。

也许 numpy 可以帮忙？

<小时/>

编辑:arr 以 [0, 0, 0] 开头调用deduceArrayFromSum(arr, 100, 0, len(arr), 100, 0)时, foundSum()使用以下参数调用:

[100, 0, 0]
[99, 1, 0]
[98, 2, 0]
[98, 1, 1]
[...]

我希望这能清除我想要的代码

Answer 1

使用itertools.combinations .

import itertools

def deduceArrayFromSum(arr, length, expectedSum):
    for combination in itertools.combinations(arr, length):
        if sum(combination) == expectedSum:
            foundSum(combination)

<小时/>

通过一些重构，我会将其变成一个生成器:

import itertools

def combinations_with_sum(iterable, length, sum_):
    return (c in itertools.combinations(iterable, length) if sum(c) == sum_)

然后你可以像这样使用它:

for t in combinations_with_sum([1, 2, 3, 4], 2, 5):
    print t

或

print list(combinations_with_sum([1, 2, 3, 4], 2, 5))

<小时/>

This problem is NP-complete ，因此对于大输入来说它总是很慢。但您可以考虑研究比暴力破解更好的算法。