Do you have some change? →
In a previous post, we saw a recursive algorithm for computing the number of ways to reach atop n stairs. Let’s do a similar computation, this time for computing the number of ways you can combine coin denominations to arrive at a given amount. More precisely:
Given a set of coin denominations and a target amount, how many ways can you combine the denominations in such a way that the combination sums up to the target amount? You can assume that you have unlimited supply of denominations.
For example, if you have unlimited supply of $1
and $2
currency bills, how many ways can you combine them to return a change for $3
? You could give three $1
bills, or a $1
bill along with a $2
bill (or alternately, a $2
bill along with a $1
bill, which is just a duplicate of the previous case just that I kept the $2
bill upon the $1
bill while giving).
Let us think recursively. Given a set S = {$1
, $2
} of bills, we could pick a $1
bill (to give) and now we have to think how many ways you can pick bills from our set S for the remaining amount of $2
($3
the target amount - $1
, the bill we already picked). Now, if you choose to pick another $1
bill, you have to think how many ways you can pick bills from our set S for the remaining amount of $1
($3
the target amount - our first picked $1
- our second $1
pick). Now, we cannot pick $2
as we need only $1
and are just left with one choice - to pick another $1
from the set. This gives us one solution { $1
, $1
, $1
}.
Alternately, we could have first picked a $2
bill and then we would be left with no choice but to pick another $1
, so that it adds up to $3
. What we are essentially doing is picking a bill whose value is less than the target amount and then computing the number of ways you can pick bills for the remaining amount, i.e. target amount - picked bill amount (our recursive step). And if this difference becomes 0, then we have a solution that sums up to the target amount (our base case for recursion).
If you try the above implementation on our example with S = { 1, 2 } and target = 3, you will get ways to be 3. And the three ways are { 1, 1, 1 }, { 1, 2 } and { 2, 1 }. What if we want only the unique ways? How would you go about modifying the above algorithm? That is we want to collapse { 1, 2 } and { 2, 1 } as just one count - after all it does not matter if I keep the $1
bill upon $2
bill or the other way around as long as I am returning bills that sum up to $3
. Think about it.