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

Jordison

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

Tentative

if you are confused in understanding the above code here is a simple version of the above code for i in range(1,len(a)): for s in itertools.combinations(a,i): if sum(s)==sum1: print(s) – Verrucose

Is there a smaller time complexity version of this code? – Amplexicaul

@Tentative : How can it be handled for more number of elements ? – Beuthen

itertools.combinations will create duplicates if numbers has duplicate elements. – Oleum

If you want to handle a large number of elements, you can restrict the numbers of elements to be combined in the parameter i of itertools.combinations(). If you know that your target should be a combination of 2 elements in the list, and pass 2 to the parameter, it should run much faster. – Maegan

Answer 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)

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

Discomfort

could you explain the line "yield from subset_sum(remaining, target, partial + [n], partial_sum + n)" – Kagoshima

@Martin Valgur : can it handle for list elements of 10000 ? – Beuthen

This will create duplicates if elements in the list are not all distinct. – Oleum

@Vepir, that is what the question requires. – Merola

Answer 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

Pop

what if you wanted each output to contain a certain number of numbers - say 12. each list needed to have 12 numbers and sum to 15? – Embezzle

@Embezzle I am looking for a similar solution like yours, have you found something? – Bengali

@Bengali I did. Don't mind my comments, but this works: # 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) – Embezzle

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

Embezzle

Answer 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

Gallous

Answer 6

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

Harlot

Answer 7

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

Merola