coin_change.py

"""
Problem
Given a value N, if we want to make change for N cents, and we have infinite supply of each of 
S = { S1, S2, .. , Sm} valued //coins, how many ways can we make the change? 
The order of coins doesn’t matter.
For example, for N = 4 and S = [1, 2, 3], there are four solutions: 
[1, 1, 1, 1], [1, 1, 2], [2, 2], [1, 3]. 
So output should be 4. 

For N = 10 and S = [2, 5, 3, 6], there are five solutions: 
[2, 2, 2, 2, 2], [2, 2, 3, 3], [2, 2, 6], [2, 3, 5] and [5, 5]. 
So the output should be 5.
"""

def count(S, n):
    # We need n+1 rows as the table is consturcted in bottom up
    # manner using the base case 0 value case (n = 0)
    m = len(S)
    table = [[0 for x in range(m)] for x in range(n+1)]
 
    # Fill the enteries for 0 value case (n = 0)
    for i in range(m):
        table[0][i] = 1
 
    # Fill rest of the table enteries in bottom up manner
    for i in range(1, n+1):
        for j in range(m):
            # Count of solutions including S[j]
            x = table[i - S[j]][j] if i-S[j] >= 0 else 0
 
            # Count of solutions excluding S[j]
            y = table[i][j-1] if j >= 1 else 0
 
            # total count
            table[i][j] = x + y
 
    return table[n][m-1]

if __name__ == '__main__':
    
    coins = [1, 2, 3]
    n = 4
    assert count(S, n) == 4
    
    coins = [2, 5, 3, 6]
    n = 10
    assert count(S, n) == 5