为何递归DFS中传递curSum+coins[i]与先修改curSum再传参结果不同？

在求解Coin Change II时，出现了一个看似奇怪的问题：直接将curSum + coins[i]作为参数传入递归调用会得到错误答案，但先执行curSum += coins[i]再传入curSum则能得到正确结果。

错误代码（测试用例target=5, coins=[1,2,5]返回6，正确应为4） #

class Solution:
    def change(self, target: int, coins: List[int]) -> int:
        self.res = 0
        def dfs(i, curSum):
            if curSum == target:
                self.res += 1
                return
            if i == len(coins) or curSum > target:
                return
            
            dfs(i, curSum+coins[i])
            dfs(i+1, curSum-coins[i])
        dfs(0,0)
        return self.res

正确代码（同一测试用例返回4） #

class Solution:
    def change(self, target: int, coins: List[int]) -> int:
        self.res = 0
        def dfs(i, curSum):
            if curSum == target:
                self.res += 1
                return
            if i == len(coins) or curSum > target:
                return
            
            curSum += coins[i]
            dfs(i, curSum)
            curSum -= coins[i] 
            dfs(i+1, curSum)
        dfs(0,0)
        return self.res           

问题根源分析 #

核心错误并非参数传递方式，而是第二个递归调用的参数逻辑完全错误：

• 正确逻辑中，当我们选择「不使用当前硬币coins[i]」时，curSum应该保持不变，直接进入下一个硬币的选择（即调用dfs(i+1, curSum)）。
• 错误代码中，第二个递归调用写了dfs(i+1, curSum-coins[i])——这毫无道理，因为我们根本没有在当前分支给curSum加过coins[i]，减法操作直接让curSum变成了负数，后续递归会产生大量不存在的非法组合（比如-1+2+2+2=5这种不符合题意的路径），最终导致计数结果偏大。

而正确代码通过回溯操作（加硬币后递归，再减回去），保证了调用第二个递归时curSum回到初始值，传递的参数完全符合「不选当前硬币」的逻辑，因此能得到正确的组合计数。

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