make_change.py

def make_change(coins, target):
      min_coins = [0 for i in range(0, target + 1)]
      sets = {i:[] for i in range(target + 1)}

      for i in range(1, target + 1):
            smallest = float("inf")
            for coin in coins:
                 if (coin <= i):
                       smallest = min(smallest, min_coins[i - coin])
                       if smallest == min_coins[i - coin]:
                             sets[i] = [coin] + sets[i - coin]
            min_coins[i] = 1 + smallest 
      
      return min_coins[target], sets[target]

print make_change([1, 5, 10, 25, 100], 165)  # => (5, [100, 25, 25, 10, 5])
print make_change([1, 3, 4], 6)  # => (2, [3, 3])