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

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

import itertoolsnumbers = [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.

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

This question has been asked before, see @msalvadores answer here. I updated the python code given to run in python 3:

def subset_sum(numbers, target, partial=[]):    s = sum(partial)    # check if the partial sum is equals to target    if s == target:        print("sum(%s)=%s" % (partial, target))    if s >= target:        return  # if we reach the number why bother to continue    for i in range(len(numbers)):        n = numbers[i]        remaining = numbers[i + 1:]        subset_sum(remaining, target, partial + [n])if __name__ == "__main__":    subset_sum([3, 3, 9, 8, 4, 5, 7, 10], 15)    # Outputs:    # sum([3, 8, 4])=15    # sum([3, 5, 7])=15    # sum([8, 7])=15    # sum([5, 10])=15