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

本文介绍了查找具有给定总和的数字列表的所有组合的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我有一个数字列表，例如

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 itertoolsbinations(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.