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 the elements in the list so that the sum of the elements equals N , and each element of the list can be added by itself with a few times. Print the amount 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

1 answer 1

The total number of options can be calculated by summing up the possible 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 to not recalculate the options already considered.