this is an example of dynamic programming
you can implement it with the standard formula for dynamic programming (see Coin Change Problem)
let s = {1,5,10,25}
our coinset for now be standard coin denominations
let f(x,y) = number_of_ways_to_make_change
let x=change_due;y=allowed_coinset_index
- notes: if y == 0 our allowed coinset is {1}, if y == 1 our allowed coinset is {1,5} ...
- any change_due has a trivial solution of 1 when our coinset consists only of {1} that is to say if you only have pennies there exists only one way to make change (all pennies)
- ergo
f(anything,0) == 1 && f(0,anything) == 1 && f(anything,anthing < 0) == 0
let us solve for a few change_due values
change_due function_call
1 f(1,0) = 1
...
4 f(4,0) = 1
5 f(5,1) = f((5-5),1) + f(5,0) = 1 + 1 = 2
...
9 f(9,1) = f(9-5,1)+f(9,0) = f(4,1) + 1 = f(4,0*) + 1 = 1+1 = 2
10 f(10,2) = f(10-10,2) + f(10,1) = f(0,2) + (f(5,1)+f(10,0))= 1+(2+1) = 4
so we can see our base cases of
f(x,0) = f(0,y) = 1
f(x is less than zero,y) = f(x,y is less than zero) = 0
note that this applies for any set of coins
V this is the important part V
#if x,y are not in above conditions we want to recursively call ourselves allowing us to build up to a complex solution from several simpler solutions
f(x,y) = f(x-CHANGE_DENOM,y) + f(x,y-1)
lets keep playing with that table from above and see how many ways we can make 16 cents
S = [1,5,10,25]
# our y is 2 (since S[2] = 10 which is the largest denomination < our change_due(16))
f(16,2) = f(16-S[2],2) + f(16,1)
= f(16-10,2) + f(16,1) = f(6,2) + f(16,1)
f(6,2) = f(6-S[2]) + f(6,1) = 0 + f( 6,1) = 0+2#(see below) =
f(16,1) = f(16-S[1],1) + f(16,0) = f(11,1) + 1
f(11,1) = f(11-S[1],1) + f(11,0) = f(6,1) + 1
f(6,1) = f(6-S[1],1) + f(6,0) = f(1,1) + 1
f(1,1) = f(1-S[1],1) + f(1,0) = 0 + 1 = 1
f(6,1) = f(1,1) + 1 = 1 + 1 = 2
f(11,1) = f(6,1) + 1 = 2 + 1 = 3
f(16,1) = f(11,1) + 1 = 3+1 = 4
f(16,2) = f(6,2) + f(16,1) = 2 + 4 = 6 ways to make change for 16 cents
now you just need to make it work for your bigger coinset