Search code examples
javascriptalgorithmdata-structures

Combination Sum using Memoiziation

I was working on LeetCode problem 39. Combination Sum:

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

As an exercise I wanted to implement memoization, but I could not make it working. So my question is:

  1. How to add memoization ?

  2. If memoization is not possible can i use child process to distribute the calculation and make it faster or is there another way?

Here is the code I started with, and which does not use memoization (note that I used a different function signature than what LeetCode expects):

function countChange(money, coins) {
  const result = [];
  function recurse(start, leftOver, selection) {
    if (leftOver < 0) return;
    if (leftOver === 0) {
      result.push(selection);
      return selection;
    }

    for (var i = start; i < coins.length; i++) {
      recurse(i, leftOver - coins[i], selection.concat(coins[i]));
    }
  }
  recurse(0, money, []);
  console.log(result);
  return result;
}

const long_result = countChange(999, [1, 2, 5, 10, 20, 50, 100]);
// const long_result = countChange(4, [1, 2]);
console.log(long_result);

I then tried adding memoization but the results were not correct. Maybe I did not implement it in the right way. Here is the code using memoization:

function countChange(money, coins) {
  const result = [];
  const memo = {};
  function recurse(start, leftOver, selection) {
    if (leftOver in memo) return memo[leftOver];
    if (leftOver < 0) return;
    if (leftOver === 0) {
      result.push(selection);
      // memo[leftOver] = selection;
      return selection;
    }

    for (var i = start; i < coins.length; i++) {
      memo[leftOver] = recurse(i, leftOver - coins[i], selection.concat(coins[i]));
    }
  }
  recurse(0, money, []);
  console.log(result);
  return result;
}

// const long_result = countChange(999, [1, 2, 5, 10, 20, 50, 100]);
const long_result = countChange(4, [1, 2]);
console.log(long_result);

After reading the comments I also tried this, but the result do not match up:

function countChange(money, coins) {
  const result = [];
  // const memo = {};
  const memo = Array(coins.length + 1)
    .fill()
    .map(() => Array(money + 1).fill(-1));
  function recurse(start, leftOver, selection) {
    if (memo[start][leftOver] != -1) return memo[start][leftOver];
    if (leftOver < 0) return;
    if (leftOver === 0) {
      result.push(selection);
      memo[start][leftOver] = selection;
      return selection;
    }

    for (var i = start; i < coins.length; i++) {
      memo[start][leftOver] = recurse(i, leftOver - coins[i], selection.concat(coins[i]));
    }
  }
  recurse(0, money, []);
  console.log(memo);
  console.log(result);
  return result;
}

// const long_result = countChange(999, [1, 2, 5, 10, 20, 50, 100]);
const long_result = countChange(4, [1, 2]);
console.log(long_result);
Solution

  • There are at least two issues:

    • The memoization should not only happen per leftOver, but also per start, as that determines which coins are still available, and that obviously influences what is still possible.

    • When you use memoization, you should make the recursive function only depend on those two dimensions (start and leftOver), not some selection. In other words, it should return (and memoize) only the selections that are made with coins that are still available. It is the responsibility of the caller to add the selections of earlier coins to that returned set of selections. That way the recursive result is not dependent on earlier selections, and memoization really represents what is selected from a certain point onwards.

    Here is your code adapted with those points taken into account:

    function countChange(money, coins) {
  // Memo per start index
  const memoPerIndex = coins.map(() => ({}));

  function recurse(start, leftOver) { // Don't pass a selection
    const memo = memoPerIndex[start]; // Get the memo relevant to this start index
    if (leftOver in memo) return memo[leftOver];
    if (leftOver < 0) return []; // Always return an array -- no results here
    if (leftOver === 0) {
      // Return one solution, which has no selections yet, as we only intend
      //    to include coins that are selected from start-index onwards.
      // It is for the caller to extend with selections of other coins.
      return [[]]; 
    }
    const result = [];
    for (var i = start; i < coins.length; i++) {
      for (const recurResult of recurse(i, leftOver - coins[i])) {
        // Extend each result with the current selected coin:
        result.push([coins[i], ...recurResult]);
      }
    }
    memo[leftOver] = result;
    return result;
  }
  return recurse(0, money);
}

const result = countChange(39, [1, 2, 5, 10, 20]);
for (const selection of result) console.log(...selection);

    Be aware that when you have more coins and greater amounts, the number of results increase exponentially. For instance,

    countChange(215, [1, 2, 5, 10, 20, 50, 100])

    ...will return over 100000 results, including many results using over 200 coins. This eats quite a lot of memory, and it quickly increases as the target amount increases. Memoization will not reduce the number of results ;-)