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

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