0

My code find all combinations of a list of numbers with a given sum. The code is working well, but when trying big numbers (like 100 or 200), the code is taking way too long.
Any advices on how to make the code much faster ?

def check(target, lst):
    def _a(idx, l, r, t):
        if t == sum(l): r.append(l)
        elif t < sum(l): return
        for u in range(idx, len(lst)):
            _a(u, l + [lst[u]], r, t)
        return r
    return len(_a(0, [], [], target))


print(check(200, (1, 2, 5, 10, 20, 50, 100, 200, 500)))
Lulzsec
  • 281
  • 2
  • 11
  • Recursion is the best choice for this kind of problems. [check out this stack overflow question](https://stackoverflow.com/questions/4632322/finding-all-possible-combinations-of-numbers-to-reach-a-given-sum). – Pramod Kumar Apr 18 '21 at 11:19

2 Answers2

2

Make the inner function simpler (only give it index and remaining target, and return the number) and then memoize it?

from functools import lru_cache

def check(target, lst):
    @lru_cache(None)
    def a(idx, t):
        if t == 0: return 1
        elif t < 0: return 0
        return sum(a(u, t - lst[u])
                   for u in range(idx, len(lst)))
    return a(0, target)

print(check(200, (1, 2, 5, 10, 20, 50, 100, 200, 500)))
Manuel
  • 912
  • 4
  • 11
0

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]
   result = [seq for i in range(len(numbers), 0, -1) for seq in 
   itertools.combinations(numbers, i) if sum(seq) == 10]
   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.

Divyanshu Parihar
  • 26
  • 1
  • 3
  • I've already seen the thread with this one code but for some reason if I give the same list as in my example & the target '42', I get '0' as result whereas I'm supposed to have 271. – Lulzsec Apr 18 '21 at 11:13