Recursion
We have a recursive function, add_coins, which has the number of free slots left for new coins, the total amount of change for this path, and the set, results, which holds the total change amounts found so far:
def add_coins(left, total, results):
"""Add combos coins to total.
If this is the last time we can add coins, return change.
Otherwise, recursively call until that condition.
>>> results = set()
>>> add_coins(left=1, total=0, results=results)
>>> results == set([1, 10])
True
"""
DIME = 10
PENNY = 1
if left == 0:
# Base Case
# We've added all the coins we're supposed to, so keep
# track of this total of change and stop recursing
results.add(total)
return
# Fork into two recursions, one adding a dime and another a penny
# For each, we'll have 1 fewer coin to add afterwards, so left -= 1
add_coins(left - 1, total + DIME, results)
add_coins(left - 1, total + PENNY, results)
This is called by coins:
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.
"""
# START SOLUTION
results = set()
add_coins(left=num_coins, total=0, results=results)
return results
There’s an easier way, though.
Imagine that you have 5 coins to spend. If you use three of them as dimes, you know that you’ll have exactly two left for use as pennies. So you can simply calculate 3 × 10 + 2 × 1 = 32.
def coins_simpler(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.
>>> coins_simpler(0) == {0}
True
>>> coins_simpler(1) == {1, 10}
True
>>> coins_simpler(2) == {2, 11, 20}
True
>>> coins_simpler(3) == {3, 12, 21, 30}
True
>>> coins_simpler(4) == {4, 13, 22, 31, 40}
True
Let's make sure it works when we can spend over 10 pennies::
>>> coins_simpler(11) == {65, 101, 38, 74, 11, 110, 47, 83, 20, 56, 92, 29}
True
"""
results = set()
for ndimes in range(num_coins + 1):
npennies = num_coins - ndimes
results.add(ndimes * 10 + npennies)
return results