coins.py

import sys

coin_cache = {}

def least_coins(coin_list, target):
  did_fit, min_coins = lc_helper(coin_list, target)
  
  if did_fit:
    return min_coins
  else:
    print "could not find anything"

def lc_helper(coin_list, target):
  if target == 0:
    return True, []
    
  if not coin_list:
    return False, []
    
  if target in coin_cache:
    return True, coin_cache[target]
    
  max_coin = coin_list[0]
  max_number = target/max_coin
  current_min_coins = sys.maxint
  return_val_coins = None
  
  for i in reversed(xrange(max_number+1)):
    total_sum = max_coin*i
    did_fit, coins_used = lc_helper(coin_list[1:], target-total_sum)
    
    if did_fit and len(coins_used) < current_min_coins:
      current_min_coins = len(coins_used)
      return_val_coins = [max_coin] * i + coins_used
      
  if return_val_coins:
    coin_cache[target] = return_val_coins
    
  return bool(return_val_coins), return_val_coins