#Coin change

#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 createMatrix(n,s):

m = [[0 for col in range(n+1)] for row in range(len(s)+1)]

#Fill first col with 1

for row in range(len(s)+1):

m[row][0] = 1

return m

def foo(n, s):

matrix = createMatrix(n, s)

for row in range(len(s)):

for col in range(n+1):

if(col < s[row]):

#Copy value from the top

matrix[row+1][col] = matrix[row][col]

else:

#add the value from top and s[row] steps behind

#why do we move those s[row] steps behind ?

#coz there is a multiple of s[row] those many steps behind and if there isnt then we still get the correct value

matrix[row+1][col] = matrix[row][col]+matrix[row+1][col-s[row]]

print matrix

print "So the total number of ways to make the change is "+str(matrix[len(s)][n])

#Main Program

foo(10, [6, 2, 5, 3])

foo(4, [1,2,3])