分治法vs回溯法：零钱兑换暴力递归解法范式归属辨析

我们以LeetCode 322. Coin Change（零钱兑换）问题为例展开讨论。
该问题的最优求解方式为动态规划，此处我们重点关注如下暴力求解（Brute Force）实现：

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        curr_min = float('inf')

        def helper(amount):
            nonlocal curr_min
        
            if amount < 0:
                return float('inf')
        
            if amount == 0:
                return 0
        
            for coin in coins:
                curr_min = min(curr_min, helper(amount-coin) + 1)
            
            return curr_min
            
        ans = helper(amount)
        return -1 if ans == float('inf') else ans

该解法对应多叉结构的递归树，树中存在大量重复的子问题节点。
从表面特征来看，该实现似乎同时符合两类经典算法范式的定义：

• 符合*分治法（Divide and Conquer）*的描述：将原问题拆解为规模更小的同结构子问题，分别求解子问题后，基于子问题结果组合得到原问题的解
• 符合*回溯法（Backtracking）*的描述：枚举所有满足约束条件的硬币选取数量组合，遍历所有可能的凑数路径
  两类算法范式均常通过递归实现，核心疑问是：上述暴力求解方案具体属于分治法还是回溯法范式？

解答 #

这个暴力实现本质是未做重叠子问题优化的自顶向下分治实现，不属于回溯法范畴，二者可以从核心设计逻辑上明确区分：

• 回溯法的核心是「路径遍历」：整个递归框架遵循「做选择→进入下一层递归→撤销选择回退」的流程，递归过程中会显式维护当前路径的选择状态，走到边界或找到合法解就回退到上一层尝试其他选项，最终遍历完所有可能的选择路径。典型的回溯问题比如全排列、子集、N皇后，代码里一定能看到状态选择、回退的明确动作。
• 这个实现完全符合分治的核心逻辑：整个递归过程没有维护「当前选了哪些硬币」的路径状态，也不存在选择后撤销的回退动作，只是把「凑出金额n需要的最少硬币数」这个原问题，拆解为「凑出n-coin面值需要的最少硬币数+1」的多个同结构子问题，取所有子问题结果的最小值作为当前问题的返回值——本质就是问题分解、子问题求解、结果合并的分治三步流程。

之所以会觉得它和回溯相似，是因为纯暴力分治遍历所有子问题的递归顺序，和回溯枚举所有组合的遍历顺序看起来重合度很高，但二者设计出发点完全不同：回溯是在遍历所有可能的选择路径找合法解，这个分治实现是在递归计算所有重叠子问题的返回值，全程没有路径状态的维护和回退操作。

补充说明：这个实现时间复杂度极高的原因，就是纯分治没有处理重叠子问题，同一个金额对应的子问题会被重复计算成百上千次，给递归加上记忆化缓存之后，就是标准的自顶向下动态规划解法。

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