查找具有给定总和的数字列表的所有组合

Question

我有一个号码列表，例如

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]]

Answer 1

您可以使用 itertools 遍历每个可能大小的每个组合，并过滤掉总和不为 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 个元素的输入列表。

Answer 2

这个问题之前有人问过，见@msalvadores 回答here。我在 python 3:

中更新了给运行的 python 代码

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

Answer 3

很棒，但我认为它作为生成器更有用：

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)

list(subset_sum([1, 2, 3, 7, 7, 9, 10], 10)) 产生 [[1, 2, 7], [1, 2, 7], [1, 9], [3, 7], [3, 7], [10]].

Answer 4

这有效...

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

Answer 5

@qasimalbaqali

这可能不是 post 正在寻找的内容，但如果您想要：

找到一系列数字[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 0 per year:')
#print(findPairs(lst, K, N)) 
findPairs(lst,K,N)

结果：

Possible monthly subscription costs that still equate to 0 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),

这背后的idea/question是"how much can we charge per month if we give x number of months free and still meet revenue targets"。

查找具有给定总和的数字列表的所有组合

Find all combinations of a list of numbers with a given sum

python

algorithm

combinations

subset-sum

python-3.x