Count no of Partitions of size at most m
Mon Dec 19 2022 20:37:00 GMT+0000 (Coordinated Universal Time)
Saved by
@akshat202002
#recursion
#python
def count_partitions(n, m):
if (n == 0 ):
return 1 # there is only 1 way i.e. to leave it unpartitioned
if (m == 0 or n < 0):
return 0 # there is no way to divide n into 0 partions or if n is -ve (latter one from edge case of recursion call of n - m)
else:
return count_partitions(n - m, m) + count_partitions(n, m - 1)
print(count_partitions(9, 5)) # 23
content_copyCOPY
# Count number of ways in which you can divide n things into partitions of at most m
- Same 5 steps.
![logic1](https://i.imgur.com/8WZQjy5.png)
![logic2](https://i.imgur.com/BiFTuAU.png)
Comments