Find all combinations of a list of numbers with a given sum

Question

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.

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

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.

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

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

How can I create a list of all combinations meeting the criteria above?

In this example, it would be [[1,2,7], [1,2,7], [1,9], [3,7], [3,7], [10]]

Answer 1

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

Result:

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

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