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

Each Answer to this Q is separated by one/two green lines.

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

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.

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
``````

@qasimalbaqali

This may not be exactly what the post is looking for, but if you wanted to:

Find all combinations of a range of numbers [lst], where each lst contains N number of elements, and that sum up to K: use this:

``````# Python3 program to find all pairs in a list of integers with given sum
from itertools import combinations

def findPairs(lst, K, N):
return [pair for pair in combinations(lst, N) if sum(pair) == K]

#monthly cost range; unique numbers
lst = list(range(10, 30))
#sum of annual revenue per machine/customer
K = 200
#number of months (12 - 9 = num months free)
N = 9

print('Possible monthly subscription costs that still equate to \$200 per year:')
#print(findPairs(lst, K, N))
findPairs(lst,K,N)
``````

Results:

``````Possible monthly subscription costs that still equate to \$200 per year:
Out[27]:
[(10, 11, 20, 24, 25, 26, 27, 28, 29),
(10, 11, 21, 23, 25, 26, 27, 28, 29),
(10, 11, 22, 23, 24, 26, 27, 28, 29),
``````

The idea/question behind this was “how much can we charge per month if we give x number of months free and still meet revenue targets”.

This works…

``````from itertools import combinations

def SumTheList(thelist, target):
arr = []
p = []
if len(thelist) > 0:
for r in range(0,len(thelist)+1):
arr += list(combinations(thelist, r))

for item in arr:
if sum(item) == target:
p.append(item)

return p
``````

The answers/resolutions are collected from stackoverflow, are licensed under cc by-sa 2.5 , cc by-sa 3.0 and cc by-sa 4.0 .