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

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.

Answer 2

The solution @kgoodrick offered is great but I think it is more useful as a generator:

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) 

list(subset_sum([1, 2, 3, 7, 7, 9, 10], 10)) yields [[1, 2, 7], [1, 2, 7], [1, 9], [3, 7], [3, 7], [10]].