Skip to content

Instantly share code, notes, and snippets.

# dblume/first_attempt.py Last active Aug 29, 2015

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 # 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])
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.