我有一个数字列表，例如：
numbers = [1, 2, 3, 7, 7, 9, 10]
如您所见，此列表中的数字可能会出现多次。
我需要获取所有这些数字的组合，它们的总和为给定值，例如10。
组合中的项目不得重复，但必须将numbers中的每个项目视为唯一，这意味着例如列表中的两个7表示具有相同值的不同项目。
顺序不重要，因此[1, 9]和[9, 1]是相同的组合。
组合的长度没有限制，[10]与[1, 2, 7]同样有效。
如何创建符合上述条件的所有组合的列表？
在此示例中，它将是[[1,2,7], [1,2,7], [1,9], [3,7], [3,7], [10]]
import itertools
numbers = [1, 2, 3, 7, 7, 9, 10]
target = 10
result = [seq for i in range(len(numbers), 0, -1)
for seq in itertools.combinations(numbers, i)
if sum(seq) == target]
print(result)
结果：
[(1, 2, 7), (1, 2, 7), (1, 9), (3, 7), (3, 7), (10,)]
遗憾的是，这个算法的时间复杂度大约为O(2^N)，所以它不适用于超过20个元素的输入列表。
@kgoodrick 提供的 解决方案 很不错，但我认为将其作为生成器更有用：
def subset_sum(numbers, target, partial=[], partial_sum=0):
if partial_sum == target:
yield partial
if partial_sum >= target:
return
for i, n in enumerate(numbers):
remaining = numbers[i + 1:]
yield from subset_sum(remaining, target, partial + [n], partial_sum + n)
输出:
print(list(subset_sum([1, 2, 3, 7, 7, 9, 10], 10)))
# [[1, 2, 7], [1, 2, 7], [1, 9], [3, 7], [3, 7], [10]]
这个问题之前已经被问过了，可以看一下@msalvadores的回答这里。我更新了给出的Python代码以在Python 3中运行：
def subset_sum(numbers, target, partial=[]):
s = sum(partial)
# check if the partial sum is equals to target
if s == target:
print("sum(%s)=%s" % (partial, target))
if s >= target:
return # if we reach the number why bother to continue
for i in range(len(numbers)):
n = numbers[i]
remaining = numbers[i + 1:]
subset_sum(remaining, target, partial + [n])
if __name__ == "__main__":
subset_sum([3, 3, 9, 8, 4, 5, 7, 10], 15)
# Outputs:
# sum([3, 8, 4])=15
# sum([3, 5, 7])=15
# sum([8, 7])=15
# sum([5, 10])=15
@qasimalbaqali
这可能不完全是帖子所寻求的，但如果您想要：
查找一系列数字范围[lst]的所有组合，每个lst包含N个元素，并且它们总和为K：请使用以下方法：
# Python3 program to find all pairs in a list of integers with given sum
from itertools import combinations
def findPairs(lst, K, N):
return [pair for pair in combinations(lst, N) if sum(pair) == K]
#monthly cost range; unique numbers
lst = list(range(10, 30))
#sum of annual revenue per machine/customer
K = 200
#number of months (12 - 9 = num months free)
N = 9
print('Possible monthly subscription costs that still equate to $200 per year:')
#print(findPairs(lst, K, N))
findPairs(lst,K,N)
结果：
Possible monthly subscription costs that still equate to $200 per year:
Out[27]:
[(10, 11, 20, 24, 25, 26, 27, 28, 29),
(10, 11, 21, 23, 25, 26, 27, 28, 29),
(10, 11, 22, 23, 24, 26, 27, 28, 29),
追加：包括零。
import random as rd
def combine(soma, menor, maior):
"""All combinations of 'n' sticks and '3' plus sinals.
seq = [menor, menor+1, ..., maior]
menor = min(seq); maior = max(seq)"""
lista = []
while len(set(lista)) < 286: # This number is defined by the combination
# of (sum + #summands - 1, #summands - 1) -> choose(13, 3)
zero = rd.randint(menor, maior)
if zero == soma and (zero, 0, 0, 0) not in lista:
lista.append((zero, 0, 0, 0))
else:
# You can add more summands!
um = rd.randint(0, soma - zero)
dois = rd.randint(0, soma - zero - um)
tres = rd.randint(0, soma - zero - um - dois)
if (zero + um + dois + tres == soma and
(zero, um, dois, tres) not in lista):
lista.append((zero, um, dois, tres))
return sorted(lista)
>>> result_sum = 10
>>> combine(result_sum, 0, 10)
输出
[(0,0,0,10), (0,0,1,9), (0,0,2,8), (0,0,3,7), ...,
(9,1,0,0), (10,0,0,0)]
This works...
from itertools import combinations
def SumTheList(thelist, target):
arr = []
p = []
if len(thelist) > 0:
for r in range(0,len(thelist)+1):
arr += list(combinations(thelist, r))
for item in arr:
if sum(item) == target:
p.append(item)
return p
for i in range(1, len(a)): for s in itertools.combinations(a, i): if sum(s) == sum1: print(s)其中itertools是 Python 中一个标准库，需要先导入。 - Abhinumbers包含重复元素，itertools.combinations将会创建重复项。 - Vepir