Recursion
You have an endless supply of dimes and pennies. How many different amounts of total change can you make using exactly num_coins number coins?
For example, when num_coins = 3, you can create 4 different kinds of change:
3 cents from penny + penny + penny
12 cents dime + penny + penny
21 cents from dime + dime + penny
30 cents from dime + dime + dime
So, you should have a function that returns the set {3, 12, 21, 30}
when num_coins is 3.
For example:
>>> coins(1) == {1, 10}
True
>>> coins(2) == {2, 11, 20}
True
>>> coins(3) == {3, 12, 21, 30}
True
>>> coins(4) == {4, 13, 22, 31, 40}
True
>>> coins(10) == {10, 19, 28, 37, 46, 55, 64, 73, 82, 91, 100}
True
We given you a file, coins.py, with a placeholder function, coin:
def coins(num_coins):
"""Find change from combinations of `num_coins` of dimes and pennies.
This should return a set of the unique amounts of change possible.
"""
Implement the coins function. When this is successful, all tests should pass.
Recursion
You can solve this problem with recursion—each time you can add a coin, you can split into two paths, one where you add a penny and one where you add a dime. This kind of recursion, where you have two “tails”, is similar to the kind you’d use to look at every node in binary tree.
There’s also a simpler, non-recursive solution. Can you find both?