python – Enumeration of the number of sums

Question:

We have input data M and N , N > M , M > 0 . After that, we create a list from 1 to M , and then we need to find all possible options for the sums of elements in the list so that the sum of the elements equals N , and each element of the list can be added to itself several times. It is necessary to display the number of sums that can be made in the list.

For example: M = 3 , N = 4 , —> [1,2,3] —> 1+1+1+1 , 1+1+2 , 1+2+1 , 2+1+1 , 2+2 , 1+3 , 3+1 , the number of possible variants of the sums in this example: 7 .

Answer:

The total number of options can be calculated by summing up the options for each admissible term in turn:

from functools import lru_cache

@lru_cache(maxsize=None)
def C(m, n):
    return sum(C(m, n - k) for k in range(1, min(m, n) + 1)) if n else 1

print(C(3, 4)) # -> 7

functools.lru_cache used so as not to recalculate the options already considered.

Scroll to Top