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

The answer of Martin Valgur allows for early exits when the target sub is already exceeded. This assumes that the input has no negative numbers.

This approach can however be extended to cover for negative values as well:

• In a preprocessing phase register for each index what the least and most possible sum can be from that point onwards
• Continue a search also after having found a good combination halfway, as it might be it could be extended further.

I would also avoid creating new lists at every recursive call. You could delay this until you really have a valid combination, and only then create a new list for it.

def subset_sum(numbers, target):
    partial = []  # Commonly shared in recursive search tree
    # Preprocessing to allow early exit, also when there are negative values in the input
    acc = 0
    least = [acc := acc + min(val, 0) for val in reversed(numbers)][::-1]
    acc = 0
    most = [acc := acc + max(val, 0) for val in reversed(numbers)][::-1]
    n = len(numbers)

    def recur(i, target):
        if i >= n or not (least[i] <= target <= most[i]):
            if target == 0:
                # Provide a new list, so that if consumer mutates it, it does not affect us
                yield partial[:]
            return  # No hope of reaching zero anymore
        yield from recur(i + 1, target)  # Combis without numbers[i] 
        partial.append(numbers[i])  # Mutate
        yield from recur(i + 1, target - numbers[i])
        partial.pop()  # Backtrack

    return recur(0, target)

# Example extended with values -6 and -10.
print(list(subset_sum([1, 2, 3, 7, 7, 9, -6, -10], 10)))

For an extended example (including values -6 and -10), this outputs the following list:

[
    [7, 9, -6], 
    [7, 9, -6], 
    [3, 7], 
    [3, 7], 
    [3, 7, 7, 9, -6, -10], 
    [2, 7, 7, -6], 
    [1, 9], 
    [1, 3, 7, 9, -10], 
    [1, 3, 7, 9, -10], 
    [1, 2, 7], 
    [1, 2, 7], 
    [1, 2, 7, 7, 9, -6, -10], 
    [1, 2, 3, 7, 7, -10]
]

Answer 2

Append: including zero.

import random as rd

def combine(soma, menor, maior):
    """All combinations of 'n' sticks and '3' plus sinals.
    seq = [menor, menor+1, ..., maior]
    menor = min(seq); maior = max(seq)"""
    lista = []

    while len(set(lista)) < 286: # This number is defined by the combination
                                 # of (sum + #summands - 1, #summands - 1) -> choose(13, 3)     
        zero = rd.randint(menor, maior)

        if zero == soma and (zero, 0, 0, 0) not in lista:
            lista.append((zero, 0, 0, 0))

        else:
            # You can add more summands!

            um = rd.randint(0, soma - zero)
            dois = rd.randint(0, soma - zero - um)
            tres = rd.randint(0, soma - zero - um - dois)


            if (zero + um + dois + tres  == soma and
             (zero, um, dois, tres) not in lista):
                lista.append((zero, um, dois, tres))

    return sorted(lista)

>>> result_sum = 10
>>> combine(result_sum, 0, 10)

Output

[(0,0,0,10), (0,0,1,9), (0,0,2,8), (0,0,3,7), ...,
(9,1,0,0), (10,0,0,0)]

Answer 3

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)

Output:

print(list(subset_sum([1, 2, 3, 7, 7, 9, 10], 10)))
# [[1, 2, 7], [1, 2, 7], [1, 9], [3, 7], [3, 7], [10]]

Answer 4

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 5

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

Answer 6

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

Answer 7

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