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

by

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.

Leave a Comment

tech