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 the same as the recursive version of Find number of ways to make coin change, but with a special 'cache' to store results. The cache key combines the remaining sum and the index of the coin currently being considered, because both values determine the remaining subproblem. 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));