Given a list of coins[] of different denominations with infinite supply of each of the coins. Find the minimum number of coins required to make the given sum. If it's not possible to make a change, return -1.

Hint

This algorithm uses memoization to improve performance. It's same as the recursive version of Find minimum coins to make change, but with a special 'cache' to store results. The 'cache key' is crucial. It's how we identify and store past results. Sometimes we need one key, sometimes multiple keys. We add code to:

# Python implementation

cache = None

def count(coins, total):
  if (total < 0 or len(coins) <= 0):
    return float('inf')
  
  if total == 0:
    return 0
  
  global cache
  if not cache:
    cache = [[None for _ in range(total + 1)] for _ in range(len(coins) + 1)]

  if not cache[len(coins)][total]:
    cache[len(coins)][total] = min(1 + count(coins, total - coins[0]), count(coins[1:], total))

  return cache[len(coins)][total]

coins = [25, 10, 5]
total = 30

coins.sort(reverse=True)

output = count(coins, total)

print(output if (output != float('inf')) else -1)

// Javascript implementation

let cache = null;

function count(coins, sum) {
  if (sum < 0 || coins.length <= 0) {
    return Infinity;
  }

  if (sum == 0) {
    return 0;
  }

  if (cache === null) {
    cache = [];

    for (let i = 0; i < coins.length + 1; i++) {
      cache[i] = [];
    }
  }

  if (cache[coins.length][sum] === undefined) {
    cache[coins.length][sum] = Math.min(1 + count(coins, sum - coins[0]), count(coins.slice(1), sum));
  }

  return cache[coins.length][sum];
}

const coins = [25, 10, 5];
const sum = 30;

coins.sort((a, b) => b - a);

const output = count(coins, sum);

console.log((output !=  Infinity) ? output : -1);

Find minimum coins to make change (Memoization)

Hint