LeetCode 39题：组合总和的记忆化实现及性能优化咨询

给定一个由不同整数组成的数组candidates和一个目标整数target，返回所有由candidates中元素组成的、和为target的唯一组合列表。组合可以按任意顺序返回。
可以从candidates中重复选择同一个数字。当至少一个所选数字的出现频率不同时，两个组合视为唯一。
测试用例保证给定输入下，和为target的唯一组合数量少于150个。

我在实现记忆化时失败了，想请教两个问题：

1. 如何正确添加记忆化？
2. 若无法使用记忆化，能否通过子进程分布式计算提升速度，或有其他优化方式？

初始无记忆化代码 #

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);

尝试记忆化但结果错误的代码 #

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);

后续尝试的二维记忆化代码（仍不符合预期） #

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);

问题解答 #

1. 如何正确添加记忆化？ #

之前的记忆化实现错误核心原因：

• 记忆化的键仅考虑leftOver或start+leftOver，但存储的是单个selection，而实际上每个(start, leftOver)对应的是一组组合，不是单个组合。
• 递归循环中会覆盖memo[start][leftOver]的值，只保留最后一次递归结果，导致丢失大部分组合。

正确的记忆化思路：
记忆化应存储从start索引开始，凑出leftOver金额的所有组合，递归函数需返回当前状态下的所有组合，而非修改外部数组。

修改后的代码示例：

function countChange(money, coins) {
  // memo[start][leftOver] 存储从start开始凑leftOver的所有组合
  const memo = Array(coins.length)
    .fill()
    .map(() => Array(money + 1).fill(null));

  function recurse(start, leftOver) {
    // 已计算过直接返回
    if (memo[start][leftOver]) return memo[start][leftOver];
    // 金额不足，返回空数组
    if (leftOver < 0) return [];
    // 金额凑齐，返回包含空数组的列表（表示当前组合结束）
    if (leftOver === 0) return [[]];

    const combinations = [];
    for (let i = start; i < coins.length; i++) {
      const coin = coins[i];
      // 递归获取子问题的所有组合
      const subCombinations = recurse(i, leftOver - coin);
      // 将当前硬币添加到每个子组合前，合并到结果中
      for (const sub of subCombinations) {
        combinations.push([coin, ...sub]);
      }
    }
    // 存储当前状态的结果到记忆化表
    memo[start][leftOver] = combinations;
    return combinations;
  }

  const result = recurse(0, money);
  console.log(result);
  return result;
}

// 测试用例
console.log(countChange(4, [1, 2])); // 输出 [[1,1,1,1],[1,1,2],[2,2]]

2. 其他优化方式与分布式计算的可行性 #

分布式计算的局限性

用子进程分布式计算提升速度意义不大：

• 题目保证组合数少于150个，即使是大目标值（如999），递归+剪枝的效率已足够，无需分布式。
• 分布式会带来进程间通信开销，反而可能拖慢速度，仅适用于超大规模计算场景，本题不满足。

其他优化方式

• 剪枝优化：先将coins排序，当当前硬币大于剩余金额时直接跳出循环（后续硬币更大，无法凑出剩余金额）。
• 迭代式动态规划：用DP表存储每个金额对应的所有组合，避免递归栈开销。示例代码：

function countChange(money, coins) {
  coins.sort((a, b) => a - b);
  // dp[i] 存储凑出金额i的所有组合
  const dp = Array(money + 1).fill().map(() => []);
  dp[0] = [[]];

  for (const coin of coins) {
    for (let amount = coin; amount <= money; amount++) {
      // 遍历凑出amount-coin的所有组合，添加当前硬币
      for (const combo of dp[amount - coin]) {
        dp[amount].push([...combo, coin]);
      }
    }
  }

  console.log(dp[money]);
  return dp[money];
}

• 减少内存拷贝：递归时避免使用concat（会创建新数组），改用传递引用+回溯的方式（递归后弹出元素），减少内存开销：

function countChange(money, coins) {
  const result = [];
  coins.sort((a, b) => a - b);

  function backtrack(start, leftOver, path) {
    if (leftOver === 0) {
      result.push([...path]); // 复制当前路径
      return;
    }
    for (let i = start; i < coins.length; i++) {
      const coin = coins[i];
      if (coin > leftOver) break; // 剪枝，后面的硬币更大，直接跳过
      path.push(coin);
      backtrack(i, leftOver - coin, path);
      path.pop(); // 回溯
    }
  }

  backtrack(0, money, []);
  console.log(result);
  return result;
}

内容的提问来源于stack exchange，提问作者FDEV