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

问题描述：

我有一个数字列表，例如

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

解决方案 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 个元素的输入列表。

解决方案 2：

这个问题之前已经问过，请参阅@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

解决方案 3：

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

解决方案 4：

@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),

这背后的想法/问题是“如果我们免费提供 x 个月并且仍然达到收入目标，我们每月可以收取多少费用”。

解决方案 5：

这有效...

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

解决方案 6：

附加：包括零。

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

解决方案 7：

Martin Valgur的答案允许在目标子项已超出时提前退出。这假设输入没有负数。

然而，这种方法可以扩展以涵盖负值：

• 在预处理阶段，为每个索引注册从该点开始的最小和最大可能的总和

• 在找到中途好的组合后，也要继续搜索，因为它可能会进一步扩展。

我还会避免在每次递归调用时创建新列表。您可以延迟此操作，直到真正拥有有效组合，然后才为其创建新列表。

def subset_sum(numbers, target):
    partial = []  # Commonly shared in recursive search tree
    # Preprocessing to allow early exit, also when there are negative values in the input
    acc = 0
    least = [acc := acc + min(val, 0) for val in reversed(numbers)][::-1]
    acc = 0
    most = [acc := acc + max(val, 0) for val in reversed(numbers)][::-1]
    n = len(numbers)

    def recur(i, target):
        if i >= n or not (least[i] <= target <= most[i]):
            if target == 0:
                # Provide a new list, so that if consumer mutates it, it does not affect us
                yield partial[:]
            return  # No hope of reaching zero anymore
        yield from recur(i + 1, target)  # Combis without numbers[i] 
        partial.append(numbers[i])  # Mutate
        yield from recur(i + 1, target - numbers[i])
        partial.pop()  # Backtrack

    return recur(0, target)

# Example extended with values -6 and -10.
print(list(subset_sum([1, 2, 3, 7, 7, 9, -6, -10], 10)))

对于扩展示例（包括值 -6 和 -10），这将输出以下列表：

[
    [7, 9, -6], 
    [7, 9, -6], 
    [3, 7], 
    [3, 7], 
    [3, 7, 7, 9, -6, -10], 
    [2, 7, 7, -6], 
    [1, 9], 
    [1, 3, 7, 9, -10], 
    [1, 3, 7, 9, -10], 
    [1, 2, 7], 
    [1, 2, 7], 
    [1, 2, 7, 7, 9, -6, -10], 
    [1, 2, 3, 7, 7, -10]
]