http://en.wikipedia.org/wiki/Change-making_problem

change_making.py

from collections import defaultdict
from itertools import islice

def make_change(target, denominations):
  """Returns fewest coins needed to make up the target value

  >>> make_change(100, [25, 10, 5, 1])
  [(25, 4)]

  >>> make_change(30, [25])
  None

  >>> make_change(50, [25, 10, 1])
  [(10, 3)]

  """
  def _explore_space(coins, target, smallest=0):
    for i, coin in islice(enumerate(coins), smallest, None):
      t = target - coin
      if t < 0:
        continue
      elif t == 0:
        yield [coin]
      else:
        for other_coins in _explore_space(coins, t, i):
          other_coins.append(coin)
          yield other_coins

  denominations = sorted(denominations, reverse=True)
  possibilities = list(_explore_space(denominations, target))
  if len(possibilities) == 0:
    return None

  possibilities.sort(key=lambda x : len(x))
  best_way = possibilities[0]

  by_coin = defaultdict(int)
  for coin in best_way:
    by_coin[coin] += 1

  return by_coin.items()