python 数组里面求和为某固定值的所有组合？

Question

如list=[2,3,4,5,6,7,8,10,12,13,23,12,34,56]
求和为22的所有组合，这个怎么实现？

Answer 1

l = [2,3,4,5,6,7,8,10,12,13,23,34,56]

def combination(l, n):
    l = list(sorted(filter(lambda x: x <= n, l)))
    combination_impl(l, n, [])

def combination_impl(l, n, stack):
    if n == 0:
        print(stack)
        return
    for i in range(0, len(l)):
        if l[i] <= n:
            stack.append(l[i])
            combination_impl(l[i + 1:], n - l[i], stack)
            stack.pop()
        else:
            break

combination(l, 22)

追问

我这是788个数据，跑了半天没跑出来！

追答

数据量太大，组合种类太多，请减少数据量。如果有重复数据请先去重。

追问

哭，哭，哭，没法减少数量！

追答

800个数据，如果其中100个可自由组合得到结果，则C(800, 100)=800!/(100!*700!)，此数字是天文数字级别，超级计算机可能都需要很多年才能输出所有组合，你的个人电脑算100年也算不完其中的1%。即便能够算出所有结果，你还需要数以万计的TB级硬盘来保存它们。

追问

非常感谢，我能问一下，你这个是只要满足了条件都输出一个？还是所有都遍历完才最后一次性输出？

追答

此方法称为回溯法，原理是将问题一步步分解为子问题并求解子问题的所有解，子问题求解完毕或无解时再向上回溯。
求解[2,3,4,5,6,7,8,10,12,13,23,34,56]中所有和为22的组合的过程是：
①求2 和 [3,4,5,6,7,8,10,12,13,23,34,56]中所有和为20的组合
②求[2,3] 和 [4,5,6,7,8,10,12,13,23,34,56]中所有和为17的组合
按此顺序递归进行求解，当最终求解完毕问题①后，向上回溯，继续求解3 和 [4,5,6,7,8,10,12,13,23,34,56]中所有和为19的组合，以此类推。

追问

嗯，是一次性输出哈！

Answer 2

L=[2,3,4,5,6,7,8,10,12,13,23,12,34,56]
d={}
n=len(L)
for i in range(n):
s=i+1
for s in range(s,n):
if L[i]+L[s]==22:
#第几位和第几位组合
print(i,s)
print(L[i],L[s])

Answer 3

for x in a: 
    for y in a: 
     if（x + y == 22）: 
        print('%d + %d = 22'% (x, y))