LeetCode 322 Coin Change：DFS递归解法调试与思路咨询

给定表示不同面额硬币的整数数组coins和总金额整数amount。
返回凑成总金额所需最少硬币数，无法凑出则返回-1，每种硬币数量无限。
示例1：输入coins=[1,2,5]，amount=11，输出3，解释：11=5+5+1
示例2：输入coins=[2]，amount=3，输出-1
示例3：输入coins=[1]，amount=0，输出0
示例4：输入coins=[1,4,5]，amount=8，输出2，解释：8=4+4

我的问题 #

我正在学习递归，想先通过DFS理解这个问题再学DP，但找不到合适的DFS解法示例。我的首次尝试在部分用例（比如coins=[186,419,83,408]，amount=6249）上失败了。以下是我的代码和思路：

代码思路 #

• 反转数组只是为了调试提速，非必要操作；
• 搭建回溯模板，遍历所有索引尝试每种选项；
• 总金额匹配目标时更新最小硬币数（可能因为未回溯导致错误）；
• 持续累加同一硬币调用回溯，直到超出金额；
• 当前路径失败时，递增索引调用回溯尝试其他硬币。

我一开始试过贪心算法但没用，想请教：怎么解决这个问题？怎么识别这类问题的模式？

我的代码 #

def coinChange(self, coins: List[int], amount: int) -> int:
    coins = coins[::-1]
    minCoin = inf
    
    def backtrack(i,total,count):
        nonlocal minCoin
        if total == amount:
            minCoin = min(minCoin,count)
            return
        
        if total + coins[i] <= amount:
            count += 1
            backtrack(i,total + coins[i],count)
        
        if i + 1 < len(coins):
            backtrack(i+1,total,count)
        
    for i in range(len(coins)):
        backtrack(i,0,0)
    return minCoin if minCoin != inf else -1

问题分析与DFS解法优化 #

你的代码有几个关键问题，导致部分用例无法通过：

1. 状态未回溯：修改count后没有恢复原值，导致后续递归调用的count值错误（比如选完当前硬币再尝试下一个硬币时，count还是加1后的数值）。
2. 缺少剪枝：没有对已经超过当前最小硬币数的路径终止计算，大金额用例下会超时甚至无法得到结果。
3. 遍历逻辑冗余：通过循环启动每个索引的回溯，导致重复计算相同组合。

修正后的DFS代码 #

def coinChange(self, coins: List[int], amount: int) -> int:
    if amount == 0:
        return 0
    # 降序排序，优先试大硬币，更快找到最优解，利于剪枝
    coins.sort(reverse=True)
    min_coins = float('inf')
    
    def dfs(index, current_total, coin_count):
        nonlocal min_coins
        # 剪枝：当前硬币数已不小于已知最小值，没必要继续
        if coin_count >= min_coins:
            return
        if current_total == amount:
            min_coins = coin_count
            return
        # 从当前索引开始遍历，避免重复组合（比如[1,2]和[2,1]视为同一组合）
        for i in range(index, len(coins)):
            coin = coins[i]
            if current_total + coin > amount:
                continue
            # 选择当前硬币，继续递归（可重复选，所以索引保持i）
            dfs(i, current_total + coin, coin_count + 1)
    
    dfs(0, 0, 0)
    return min_coins if min_coins != float('inf') else -1

关键优化点 #

• 无状态修改的递归：通过传递coin_count + 1而非修改原变量，避免了回溯时的状态污染。
• 剪枝操作：当当前硬币数已经大于等于已知最小值时，直接终止路径，减少无效计算。
• 降序排序：优先尝试大面额硬币，能更快找到较优解，让剪枝更早生效，大幅提升效率。
• 去重遍历：从当前索引开始遍历，避免重复计算顺序不同的相同组合。

问题模式识别 #

这类问题属于无限背包问题（每种物品可重复选择），核心是求最优解（最少硬币数）。贪心算法无效的原因是硬币面额不满足贪心选择性质（比如示例4中，贪心选5+1+1+1需要4个，最优却是4+4仅需2个）。

当遇到求「最少/最多」「是否存在」的组合类问题时，若贪心无效，可优先考虑：

• DFS（回溯）：适合理解问题本质，但必须配合剪枝避免超时；
• 动态规划：适合处理大规模数据，通过状态转移记录中间结果，彻底避免重复计算。

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