Given a list of numbers, find the first combination of numbers that adds up to a certain sum.

Example:

Given list: [1, 2, 3, 4, 5] Given sum: 5 Response: [1, 4] the response can also be [2, 3], it doesn't matter. What matters is that we get a combination of numbers from the given list that adds up to the given sum as fast as possible.

I tried doing this with itertools.combinations in python, but it takes way too long:

from typing import List
import itertools

def test(target_sum, numbers):
    for i in range(len(numbers), 0, -1):
        for seq in itertools.combinations(numbers, i):
            if(sum(seq) == target_sum):
                return seq


if __name__ == "__main__":
    target_sum: int = 616
    numbers: List[int] = [16, 96, 16, 32, 16, 4, 4, 32, 32, 10, 16, 8, 32, 8, 4, 16, 8, 8, 8, 16, 8, 8, 8, 16, 8, 16, 16, 4, 8, 8, 16, 12, 16, 16, 8, 16, 8, 8, 8, 8, 4, 32, 16, 8, 32, 16, 8, 8, 8, 8, 16, 32, 8, 32, 8, 8, 16, 24, 32, 8]

    print(test(target_sum, numbers))

CodePudding user response：

def subsum(tsum, numbers):
    a = [0]*(tsum 1)
    a[0] = -1
    for x in numbers:
        for i in range(tsum, x-1,-1):     #reverse to avoid reusing the same item
            if a[i-x] and a[i] == 0:        #we can form sum i with item x and existing sum i-x
                a[i] = x      #remember the last item for given sum
    res = []
    idx = tsum
    while idx:
        res.append(a[idx])
        idx -= a[idx]
    return res

print(subsum(21, [2,3,5,7,11]))

>>>[11, 7, 3]

When the last cell is nonzero, combination does exist, and we can retrieve items.

Complexity is O(target_sum*len(numbers))