Finds how many ways n objects can be partitioned into groups of at most size m

CountPartitions.py

###################################################################
#Partition Count
#Write a function that counts the number of ways you can
#partition n objects using parts up to m assuming m >= 0
#
#
#Based on videos from Reducible
#Partition Count: https://www.youtube.com/watch?v=ngCos392W4w
###################################################################

#The total number of partitions is the sum of the partitions with n-m objects using
#up to m parts, partition(n-m,m) and the partitions of n objects using up to m-1
#parts, partition(n,m-1). The computations can be carried out recursively or
#iteratively. Reducible showed the recursive version, I derived the iterative version

#Base cases:
#           n == 0 means no objects availble so only 1 way to partition, empty set
#           m == 0 each partition must have 0 elements. Impossible so 0 partitions
#           n < 0 only to prevent errors dealing cases when n-m < 0

#Recursive version
def countPartitions(n, m):
    if n == 0:
        return 1
    if m == 0 or n < 0:
        return 0
    return countPartitions(n, m-1)+countPartitions(n-m, m)

#Loop version
def countPartitionsIter(n,m):
    #Initialise Table to store values
    #1st row & 1st columns are set to 1 since there's
    #only 1 partition when m = 1 or n = 1
    table = [[0 for i in range(0,n)] for j in range(0,m)]
    table[0] = [1 for i in range(0, n)]
    for i in range(1, m):
        table[i][0] = 1

    #Under represents the partitions when the size of the partition is at most
    #m-1. On the table this is the value on the previous row and same column.
    #Matches with countPartitions(n,m-1).
        
    #Prev represents the partitions when assuming one partition is of size m.
    #On the table this is the value on the same row and m elements before.
    #Matches with countPartitions(n-m,m).
        
    for i in range(1, m):
        for j in range(1, n):
            under = table[i-1][j]
            
            if j-i < 0: #when n < 0 otherwise negative values throw off computations
                prev = 0
            elif j-i == 0: #when n = 1
                prev = 1
            else:
                prev = table[i][j-i-1]
            table[i][j] = under + prev
    return table[m-1][n-1]

#Code below for testing purposes. Remove triple quotations to run
"""
print(countPartitions(5,3))
print(countPartitions(9,5))
print(countPartitions(7,4))
print(countPartitions(6,4))
print(countPartitionsIter(5,3))
print(countPartitionsIter(9,5))
print(countPartitionsIter(7,4))
print(countPartitionsIter(6,4))
"""