How to output the actual coin combination in the minimum change problem using recursion

Question

Given a list of coin denominations and a target value, I'm trying to make a recursive function that will tell me the smallest possible number of coins I'd need to make that value, and to then show which coins I'd need. eg input coins [1,5,10,25] and target of 6, output should be "You need 2 coins: [1,5]" I've written a function that tells me how many coins I'd need, but I want to see what the coin combination would be too.

# USD - $1, $5, $10, etc.
currency = [1, 5, 10, 20, 50, 100]

# the amount to change - eg $6
amount = 6

cache = dict() 

def recursive_change(currency, amount):
  if amount in cache.keys() is not None:
    return cache[amount]

  # base case
  if amount == 0:
    return 0

  result = amount+1 # initially result is just some high number 
  #I figure amount + 1 is fine because we'd never use more coins than the value (assuming we can't have coins worth less than one)

  for coin in currency:
    if coin <= amount:
      result = min(result, recursive_change(currency, amount-coin) + 1)
  cache[amount]=result
  return result

Here's another version I just made - I noticed my initial solution didn't handle impossible inputs well (eg make 6 cents using only nickels and dimes), so now it returns -1 for impossible amounts. It's a bit uglier though, would love some input on making it nicer.

def recursive_change(currency, amount):
  if amount in cache.keys():
    return cache[amount]

  # base case
  if amount == 0:
    return 0

  # If we can't make the amount with this coin, return -1
  if amount < 0:
    return -1

  result = -1

  for coin in currency:
    if coin <= amount:
      current_result = recursive_change(currency, amount-coin) 
      if current_result >= 0: 
        if result < 0:
          result = current_result 
        else: 
          result = min(current_result, result) 

  if result < 0:
    result = -1
  else:
    result = result + 1
  cache[amount]=result
  print(cache)
  return result

Answer 1

This solution uses recursion to find the ideal solutions where the greedy algorithm fails, uses a cache so it should be about as fast as the DP iterative approach, and outputs the actual coin combination.

# currency denominations
currency = [2,3,15,25]

# the amount to make change for - eg $30
amount = 30

# cache contains the best currency combos for each value: eg cache[7]=[5,1,1]
cache = dict()
def recursive_change(currency, amount):
  if amount in cache.keys():
    return []+cache[amount] # Had to do this [] thing so it passes a copy

  # base case
  if amount == 0:
    return []

  # If we can't make the amount with this coin, return -1
  if amount < 0:
    return [-1]

  best_combo = [-1]

  for coin in currency:
    current_result = recursive_change(currency, amount-coin)
    if current_result == [] or current_result[0] >= 0: 
      current_result.append(coin)  # if we picked a coin, we add it to the list
      if best_combo[0] < 0:
        best_combo = current_result 
        # if we found the first coin combo that works for the current problem, set best so we don't compare to -1 below
      else: 
        # if this isn't the first coin combo that works for the current problem, check to see if it's better than any of the other coin combos
        if len(current_result) < len(best_combo):
          best_combo = current_result

  cache[amount]=[]+best_combo # Had to do this [] thing so it passes a copy
  return best_combo

Answer 2

You approach is very inefficient, especially for large sums of money. You should have started generating sums from the highest denominations, not from the lowest. Here's the faster and simpler version that returns the denomination and the number of coins/bills:

currency = [1, 5, 10, 20, 50, 100]

def recursive_change(currency, amount):
    for c in reversed(currency) :
        if amount >= c :
            return [(amount // c, c),] + recursive_change( currency, amount % c )
    return []

recursive_change( currency, 6 )
>>> [(1, 5), (1, 1)]

that means one coin of 5 and one coin of 1.

A couple more of test results:

>>> recursive_change( currency, 77 )
[(1, 50), (1, 20), (1, 5), (2, 1)]
>>> recursive_change( currency, 99 )
[(1, 50), (2, 20), (1, 5), (4, 1)]