查找具有给定总和的数字列表的所有组合 [英] Find all combinations of a list of numbers with a given sum

问题描述

我有一个数字列表，例如

I have a list of numbers, e.g.

numbers = [1, 2, 3, 7, 7, 9, 10]

如您所见，数字在此列表中可能会出现多次。

As you can see, numbers may appear more than once in this list.

我需要获取具有给定总和的这些数字的所有组合，例如 10 。

I need to get all combinations of these numbers that have a given sum, e.g. 10.

组合中的项目可能不会重复，但是数字中的每个项目都必须唯一对待，即意味着列表中的两个 7 表示具有相同值的不同项目。

The items in the combinations may not be repeated, but each item in numbers has to be treated uniquely, that means e.g. the two 7 in the list represent different items with the same value.

顺序并不重要，因此 [1，9] 和 [9，1] 是相同的组合。

The order is unimportant, so that [1, 9] and [9, 1] are the same combination.

组合没有长度限制， [10] 与 [1、2、7]一样有效。

There are no length restrictions for the combinations, [10] is as valid as [1, 2, 7].

如何创建满足上述条件的所有组合的列表？

在此示例中，它是 [[1,2,7]，[1,2,7]，[1,9]，[3,7]，[ 3,7]，[10]]

推荐答案

您可以使用itertools遍历每个组合每种可能的大小，并过滤掉所有不等于10的内容：

You could use itertools to iterate through every combination of every possible size, and filter out everything that doesn't sum to 10:

import itertools
numbers = [1, 2, 3, 7, 7, 9, 10]
result = [seq for i in range(len(numbers), 0, -1) for seq in itertools.combinations(numbers, i) if sum(seq) == 10]
print result

结果：

[(1, 2, 7), (1, 2, 7), (1, 9), (3, 7), (3, 7), (10,)]

不幸的是，这有点像O（2 ^ N）复杂度，所以它不是不适合大于20个元素的输入列表。

Unfortunately this is something like O(2^N) complexity, so it isn't suitable for input lists larger than, say, 20 elements.

这篇关于查找具有给定总和的数字列表的所有组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！