Create a gist now

Instantly share code, notes, and snippets.

Ways to Break a Dollar into Change
def ways_to_break(amount, coins):
"""
:param amount: the monetary value to break into some number of coins
:param coins: a container of descending coin denominations
:return: the number of different ways to break amount into coins
"""
this_coin = coins[0]
# If this is the only coin, there's one way to break it.
if len(coins) == 1:
return 1
# Note range is never empty, we always want to try with 0 of this coin.
total = 0
for coin_value in range(0, amount+1, this_coin):
total += ways_to_break(amount - coin_value, coins[1:])
return total
print ways_to_break(100, (100, 50, 25, 10, 5, 1))
def ways_to_break(amount, coins):
"""
:param amount: the monetary value to break into some number of coins
:param coins: a mutable container of coin denominations
:return: the number of different ways to break amount into coins
"""
this_coin = coins.pop()
# If that was the only coin, see if it can break amount.
if not coins:
if amount % this_coin:
return 0
else:
return 1
# For every time this coin denomination could be used (including zero),
# get the number of ways to break the remaining amount with only the
# remaining coins.
return sum([ways_to_break(amount - coin_value, coins[:])
for coin_value in range(0, amount+1, this_coin)])
# The list of coins doesn't have to be ordered now, but there'll
# be fewer calls if the biggest denominations are processed first.
print ways_to_break(100, [1, 5, 10, 25, 50, 100])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment