Getting all combination of calculating X given a list of numbers

Question

Pretty simple idea but harder (for me) in code.

I want to know how many combinations there are to calculate a number X given the numbers I can calculate it from.
Here's an example :

>>> calculate(5, (1,2,5))
4
>>> calculate(42, (1,2,5,10,20))
271

The first example gives 4 because :

5
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

I'm pretty sure this can be done the fast using dynamic programmation or recursive with memorization but can't think of a way of starting the whole thing.

Edit
I want to do this : Find all combinations of a list of numbers with a given sum But for some unknown reason, most of code don't works and other can't even do the simple example of 5 I gave or numbers like 42.

Does this answer your question? [Find all combinations of a list of numbers with a given sum](https://stackoverflow.com/questions/34517540/find-all-combinations-of-a-list-of-numbers-with-a-given-sum) — Henry Ecker, Apr 18 '21 at 01:36
This is exactly what I want but these codes aren't working, some simply don't work, some works for some numbers but not all ( they don't do the simple example I gave for example ) — Lulzsec, Apr 18 '21 at 01:56
Does this answer your question? [Finding Combinations to the provided Sum value](https://stackoverflow.com/questions/20193555/finding-combinations-to-the-provided-sum-value) — msanford, Apr 18 '21 at 02:27

score 1 · Answer 1 · answered Apr 18 '21 at 02:24

Found it! Everything is on StackOverflow :p
Code from there:

def subsets_with_sum(lst, target, with_replacement=False):
    x = 0 if with_replacement else 1
    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 + x, l + [lst[u]], r, t)
        return r
    return _a(0, [], [], target)

Ajax1234 · Accepted Answer · 2021-04-18T02:47:04.097

You can use a function that finds all divisors of the desired sum in the input list:

def calculate(v, d, c = []):
   if not v:
      yield tuple(sorted(c))
   elif v > 0:
      vals = [i for i in d if not v%i] #find divisors
      for i in vals:
         for j in range(1, int(v/i)+1):
            #run offset by subtracting the current divisor iteration by the running total "v" 
            yield from calculate(v - (i*j), [x for x in d if x != i], c + ([i]*j))
      if not vals: #no divisors found
         for i in d:
             yield from calculate(v - i, d, c+[i])

print(len(set(calculate(5, (1,2,5)))))
print(len(set(calculate(42, (1,2,5,10,20)))))
print(len(set(calculate(15, (9, 6))))) #example with no divisors

Output:

4
271
1

Getting all combination of calculating X given a list of numbers

2 Answers2