Coin Changing

This code finds all ways of making change for a given amount using the specified denominations. For example, if we had use of an infinite supply of pennies, nickels, dimes, and quarters, then the best way to make change for 33 cents is 1 quarter, 1 nickel, and 3 pennies.

def change(n, coins_available, coins_so_far):
 if sum(coins_so_far) == n:
  yield coins_so_far
 elif sum(coins_so_far) > n:
  pass
 elif coins_available == []:
  pass
 else:
  for c in change(n, coins_available[:], coins_so_far+[coins_available[0]]):
   yield c
  for c in change(n, coins_available[1:], coins_so_far):
   yield c

if __name__ == '__main__':
 n = 33
 coins = [1, 5, 10, 25]

 solutions = [s for s in change(n, coins, [])]
 for s in solutions:
  print s

 print 'optimal solution:', min(solutions, key=len)

Below is the output, showing all ways of making change for 33 cents using only coins worth 1, 5, 10, and 25 cents.