Find how many ways you can make change with infinite amount of coins c = [c1, c2, ..., cm] for change N

CoinChangeWays.py

############################################################################
#Find how many ways you can make change with coins c = [c1, c2, ..., cm]
#for change N. Similar to the Subset Sum problem
#
############################################################################

#Dynamic Programming Solution
def cchange(Cents, coins):
    #Initialize matrix to store values
    matrix = [[0 for i in range(0, cents+1)] for j in range(0, len(coins)+1)]
    for i in range(0, len(coins)+1): matrix[i][0] = 1

    for i in range(1,len(coins)+1): #Iterate through all coins 0 coins - all coins
        for j in range(0, cents+1): #Iterate through all possible total change 0 - cents
            x = matrix[i-1][j]  #When solution doesn't include current coin
            y = 0
            if j-coins[i-1] >= 0:
                y = matrix[i][j-coins[i-1]] #When solution includes current coin
            
            matrix[i][j] = x+y #Combine both solutions
    
    return matrix

#Recursive Solution
def coinchange(N, S, m):

    if N < 0:
        return 0
    if N == 0:
        return 1

    if m <= 0 and N >= 1:
        return 0
    
    c1 = coinchange(N, S, m-1)
    c2 = coinchange(N-S[m-1], S, m)

    return c1 + c2

def printMat(matrix):
    for i in matrix:
        print(i)

coins = [1, 2, 3]
cents = 5
print("Test 1:")
c = coinchange(cents, coins, 3)
x = cchange(cents, coins)
print("Final matrix with coins ", coins, " and ", cents, " cents is ")
printMat(x)
print("c = ", c, " and x = ", x[len(coins)][cents])
print("")

coins = [1, 3, 5, 6]
cents = 10
print("Test 2:")
c = coinchange(cents, coins, 4)
x = cchange(cents, coins)
print("Final matrix with coins ", coins, " and ", cents, " cents is ")
printMat(x)
print("c = ", c, " and x = ", x[len(coins)][cents])
print("")