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

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

原文由 Byte Commander 发布，翻译遵循 CC BY-SA 4.0 许可协议

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

原文由 Kevin 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

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

原文由 Martin Valgur 发布，翻译遵循 CC BY-SA 4.0 许可协议