Find number of way to make coin change (Memoization)

Given a list of coins[] representing different denominations, count all combinations of the coins to make a given value sum.

Hint

This algorithm uses memoization to improve performance. It's same as the recursive version of Find number of way to make coin 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:

• Initialize cache to store results.
• Using the key to check cached result. If the result is not found in the cache, do the calculation and save the result in cache.
• Return the cached result.

• Python
• Javascript
•  Run

cache = None

def count(coins, total):
  if (total < 0 or len(coins) <= 0):
    return 0

  if total == 0:
    return 1

  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] = count(coins, total - coins[0]) + count(coins[1:], total)

  return cache[len(coins)][total]

coins = [1, 2, 3]
total = 4

print(count(coins, total))

let cache = null;

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

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

  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] = count(coins, sum - coins[0]) + count(coins.slice(1), sum);
  }

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

const coins = [1, 2, 3];
const sum = 4;

console.log(count(coins, sum));