Skip to content

Instantly share code, notes, and snippets.

@marcodebe
Last active April 23, 2019 20:46
Show Gist options
  • Save marcodebe/567776b1b692548c818eb296d0533e8e to your computer and use it in GitHub Desktop.
Save marcodebe/567776b1b692548c818eb296d0533e8e to your computer and use it in GitHub Desktop.
SICP problem on counting change - in python
"""
How many different ways can we make change of $1.00, given half-dollars,
quarters, dimes, nickels, and pennies?
"""
KINDS_OF_COINS = [1, 5, 10, 25, 50]
def count_change(amount, coins):
"""
Returns the number of ways to change an amount having coins
"""
if amount == 0:
return 1
if amount < 0 or coins == []:
return 0
return (count_change(amount, coins[:-1]) +
count_change(amount - coins[-1], coins))
print(count_change(100, KINDS_OF_COINS))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment