Count no of Partitions of size at most m

PHOTO EMBED

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)