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

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

Answers:

Thank you for visiting the Q&A section on Magenaut. Please note that all the answers may not help you solve the issue immediately. So please treat them as advisements. If you found the post helpful (or not), leave a comment & I’ll get back to you as soon as possible.

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

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

Method 3

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

Method 4

@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”.

Method 5

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

All methods was sourced from stackoverflow.com or stackexchange.com, is licensed under cc by-sa 2.5, cc by-sa 3.0 and cc by-sa 4.0