回溯算法：剪枝的艺术

2.3 回溯算法：剪枝的艺术

本节摘要：回溯回答的是"把所有方案都列出来"这类问题。本节以全排列与子集为模板讲透"选择、递归、撤销选择"的三步循环，画出解空间树的形状，重点演示剪枝条件如何把指数级解空间实际砍到可运行，并总结回溯与动态规划的分野。

当答案不是最优值，而是全部方案

上一节动态规划利用重叠子问题"记"住了重复劳动；但很多问题要的恰恰是所有不同的方案——全排列、所有子集、所有满足条件的组合——这些方案的列表本身就是答案，无法合并、无法记忆。解空间从表格退化成一棵巨大的树：每个决策点分出若干分支，每个叶子是一个完整方案。回溯就是在这棵树上做深度优先遍历，走到底收答案，走不通退回来换条路。它的复杂度天然是指数或阶乘级——这不是实现差，是输出本身就那么大——所以本节的进化关键词只有一个：剪枝，在死路上的分支还没展开之前就掐断它。

先看模板。回溯函数围绕三步循环展开：做选择（把候选放进路径）、递归（带着新路径深入下一层）、撤销选择（把候选弹出，恢复现场）。现场恢复是回溯的灵魂，漏了它，共享的路径数组就会把错误状态带进兄弟分支。

def permute(nums):
    res, path, used = [], [], [False] * len(nums)

    def backtrack():
        if len(path) == len(nums):        # 收集完整方案
            res.append(path[:])           # 必须拷贝，path 是共享的
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True                # 做选择
            path.append(nums[i])
            backtrack()                   # 深入
            path.pop()                    # 撤销选择
            used[i] = False

    backtrack()
    return res

print(permute([1, 2, 3]))
# 输出 [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
​

全排列的解空间是 n 的阶乘：n 等于 3 时 6 个方案，n 等于 10 时三百六十多万个。递归深度 n、每层分支递减，这个输出规模没法优化——要所有方案就得付这个代价。

一、子集与组合：去重的两种口径

子集问题换个形态：每个元素只有选或不选两种命运，解空间是 2 的 n 次方。回溯同样适用，只是收集时机变了——全排列在叶子收集，子集在每个节点都收集。组合问题（从 n 个里选 k 个）则要在循环起点上做文章：传个 start 参数，只向后选，避免同一组合的不同顺序被重复计入。

def subsets(nums):
    res, path = [], []

    def backtrack(start):
        res.append(path[:])               # 每个节点都是一个子集
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1)              # 只向后走，天然去重
            path.pop()

    backtrack(0)
    return res

print(subsets([1, 2, 3]))
# 输出 [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
​

若输入含重复元素而答案要求方案互异，标准手法是先排序、再在同层循环里跳过与前一个相等的候选——排序让相同元素相邻，跳过同层重复但不禁止不同层的重复。这几行去重代码是回溯题的最高频考点，逻辑务必亲手推一遍而不是背下来。

二、剪枝：让指数级真正可运行

模板跑通只是起点，回溯的实际性能完全取决于剪枝。以组合总和为例：候选数组 candidates 与目标 target，允许重复选用，列出所有和为 target 的组合。朴素回溯会枚举一切可能性；剪枝版先排序，递归中一旦当前和加上最小候选都超过剩余目标，直接终止整层循环——后面的候选更大，全都不用试。

def combination_sum(candidates, target):
    candidates.sort()
    res, path = [], []

    def backtrack(start, remain):
        if remain == 0:
            res.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remain:    # 剪枝：排序后后面全超
                break                     # break 而非 continue，整层放弃
            path.append(candidates[i])
            backtrack(i, remain - candidates[i])   # i 不加一，允许重复选
            path.pop()

    backtrack(0, target)
    return res

print(combination_sum([2, 3, 6, 7], 7))   # 输出 [[2, 2, 3], [7]]
​

剪枝条件从哪里来？从问题的结构性约束来：候选有序所以可以 break（结构性剪枝）、剩余和为负所以无解（可行性剪枝）、当前部分解与历史方案必然同构所以跳过（对称性剪枝，如全排列去重）、估值函数断定从当前局面到不了目标（启发式剪枝，数独与八皇后常用）。写回溯题的正确节奏：先写不剪枝的版本确认逻辑正确，再逐个加剪枝条件并用对比测试确认结果不变。八皇后是检验剪枝功力的终极练习——用三个集合记录已占用的列与两条对角线，冲突分支零展开，64 格棋盘瞬间出解。

回溯与动态规划的分野一句话讲清：要所有方案用回溯（方案无法合并），只要最优值且子问题重叠用动态规划（重叠可以记忆）。边界情况是"要最优值但子问题不重叠"，这时两者都退化，老老实实搜索加剪枝就是最优解法。

本节要点回顾

• 三步循环：做选择、递归、撤销选择，现场恢复不彻底必出鬼；
• 收集时机：排列在叶子收集，子集在每个节点收集，组合靠 start 参数去重；
• 含重复输入的去重：先排序，同层跳过相邻相同候选；
• 剪枝四类：结构性 break、可行性掐断、对称性跳过、启发式预判，性能全靠它们；
• 与 DP 的分野：要全部方案选回溯，要最优值且子问题重叠选动态规划。

下一节讲一个反方向的故事：有些问题根本不需要拆，数据自带的单调性让两个指针一路扫过去就能完成优化——双指针与滑动窗口。