We have input data
N > M ,
M > 0 . After that, we create a list from
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.
M = 3 ,
N = 4 , —>
3+1 , the number of possible variants of the sums in this example:
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.