Coin Change II问题疑惑：为何「取当前硬币并移至下一个」思路多余？

问题背景 #

给定表示不同面额硬币的整数数组coins，以及表示总金额的整数amount，返回组成该金额的组合数（无法组成则返回0），假设每种硬币数量无限。

最初的错误思路与代码 #

最初的思路是对每个索引位置定义三种选择：

• 取当前索引的硬币，留在当前索引
• 取当前索引的硬币，移动到下一个索引
• 不取当前索引的硬币，移动到下一个索引

对应的错误代码：

var change = function(amount, coins, index = 0) {
    if(amount === 0) return 1;
    if(index >= coins.length|| amount < 0)  return 0;

    let way1 = change(amount - coins[index], coins, index);
    let way2 = change(amount - coins[index], coins, index+1);
    let way3 = change(amount, coins, index+1);

    return way1 + way2 + way3;
};

console.log(change(3, [1,2,5])) // 输出结果大于正确值

修正后的正确代码 #

去掉第二种选择并加入记忆化优化后，代码通过测试：

var change = function(amount, coins, index = 0, memo={}) {
    if((amount+','+index) in memo) return memo[amount+','+index];
    if(amount === 0) return 1;
    if(index >= coins.length|| amount < 0)  return 0;

    let way1 = change(amount - coins[index], coins, index, memo);
    let way2 = change(amount, coins, index+1, memo);

    memo[amount+','+index] = way1 + way2;
    return memo[amount+','+index];
};

console.log(change(5, [1,2,5])) // 输出正确值4

为什么第二种选择会导致重复计数？ #

核心原因是：第二种选择的场景已经被剩余两种选择的递归分支覆盖，且会产生完全重复的组合。

正确的递归逻辑应该将所有组合分成互斥且全覆盖的两类：

1. 使用当前硬币（可重复使用，因此留在当前索引继续递归）
2. 不使用当前硬币（直接跳到下一个索引，后续不再考虑当前硬币）

你原来定义的第二种选择「取当前硬币并移动到下一个索引」，本质是「使用一次当前硬币，之后再也不使用它」。但这个场景已经包含在第一种选择的递归分支里：
比如在way1的递归中，先取一次当前硬币，后续递归时选择「不取当前硬币（跳到下一个索引）」，最终得到的组合和第二种选择的结果完全一致，这就导致同一个组合被多次累加计数。

举个具体例子：amount=3，coins=[1,2]

• 原思路的way2：取1，跳到索引1，剩余金额2，取2，得到组合[1,2]
• 原思路的way1：取1，留在索引0，剩余金额2；在这个递归分支里选择「不取1，跳到索引1」，取2，得到组合[1,2]

两个分支计算了同一个组合，最终结果会重复累加，导致返回值错误。

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