LeetCode 46. 全排列：回溯算法的第一课

全排列（LeetCode 46，Medium）是回溯算法的第一课：给一组互不相同的整数，输出所有全排列。它之所以是「第一课」，是因为它的解法结构——选择 → 递归 → 撤销的三步循环——是所有回溯题（子集、组合、N 皇后、数独、单词搜索）的共同骨架；学会这一课，回溯的大门就开了。

回溯骨架：选择、递归、撤销

回溯的本质是对一棵「决策树」做深度优先遍历：树的每一层做一个决策（这一位放哪个数），叶子是完整解（排满了）。代码骨架：

def permute(nums: list[int]) -> list[list[int]]:
    result, path, used = [], [], [False] * len(nums)

    def backtrack():
        if len(path) == len(nums):        # 叶子：排满了
            result.append(path[:])        # 注意拷贝！path 会被继续修改
            return
        for i in range(len(nums)):
            if used[i]:                   # 剪枝：已在当前排列中的数字跳过
                continue
            used[i] = True                # 1. 选择
            path.append(nums[i])
            backtrack()                   # 2. 递归（进入下一层决策）
            path.pop()                    # 3. 撤销（回溯的"溯"）
            used[i] = False

    backtrack()
    return result

三个初学者必须理解的点：其一，path[:] 的拷贝——path 是一条不断被修改的工作路径，存入结果必须拷贝快照，直接 append(path) 存的是同一个引用（最后全是空列表——回溯最著名的初学者 bug）。其二，撤销的对称性——选择时改了什么（used[i]=True、path.append），撤销时就还原什么，一步不多一步不少；回溯的"溯"字，就是「撤销到决策前的状态」。其三，复杂度的直觉——n 个数的全排列有 n! 个，每个长 n，总时间 O(n × n!)；回溯的复杂度由解的数量决定，优化空间极小（解就该全输出），它考的是「不重不漏」的正确性。

与「去重剪枝」的关系：这题不需要，但它很重要

全排列的输入「互不相同」，所以每个数字用没用（used 数组）就足以保证不重不漏——不需要额外的去重剪枝。但当输入含重复数字（LeetCode 47「全排列 II」）时，同一排列会被生成多次（两个相同的 1 分别占第一位，产生两个相同排列），需要排序 + 同层去重剪枝：同层决策中，「与前一个相同的数字，若前一个未使用则跳过」——一句剪枝（if i > 0 and nums[i] == nums[i-1] and not used[i-1]: continue）消灭所有重复分支。「排序后同层跳过重复」是回溯去重的通用模式，在子集 II、组合总和 II 中反复出现——它是回溯第一课的必带笔记：第一课先学骨架，第二课（去重）马上就来。

从全排列到子集：两种决策树的差异

回溯家族的两大分支，差异在决策树的形状。排列树（全排列）：每一层的决策是「从剩余数字里选一个」——顺序有意义，[1,2] 与 [2,1] 是两个解；每层的选择范围由 used 控制。子集树（LeetCode 78 子集）：每一层的决策是「第 i 个元素选还是不选」——顺序无意义，{1,2} 与 {2,1} 是同一个集合；为了避免重复，强制「只往后选」（递归传入起始下标，每层从 start 开始）。组合（LeetCode 77 组合总数）介于两者：同样是「往后选」+ 固定长度。一句话总结三种决策树：排列用 used 数组、子集与组合用 start 下标；排列的解是「顺序」，子集组合的解是「选择」——理解了这个差异，回溯家族的题目在脑海里就自动分成了两棵树。

递归树的「数量感知」：为什么回溯不怕 n=10 怕 n=25

全排列的决策树有 n! 个叶子，对 n=25 这是天文数字——但全排列题的输入约束就是 n ≤ 8 左右（题目给的），而 N 皇后的 n 可以到 9（LeetCode 约束）——回溯题的可行性与输入规模强绑定，这也是识别「该不该用回溯」的第一直觉：看到 n ≤ 20 的数据范围，回溯/状压的雷达就该亮了（数据范围是出题人给你的算法提示——这是竞赛圈的老话）。数量感知的第二层：剪枝的威力要用「剪掉的子树大小」度量。N 皇后的位运算剪枝，第一行剪掉约一半的列选择，第二行又剪掉大半——剪枝的有效性随深度累乘：第一层的坏选择砍掉整个子树（约 (n-1)! 的叶子），这就是「约束检查前置于递归」的收益量化。数量感知的第三层：解的数量与搜索树的大小的区别——全排列的解有 n! 个（输出本身就 O(n×n!)），搜索树大小也是 n! 级（几乎无剪枝空间）；N 皇后 8 皇后只有 92 个解，但搜索树远大于 92（大量分支被剪掉）——输出的成本与搜索的成本是两本账，优化各走各的路。

回溯的三种输出：全输出、计数、最优解

回溯家族的输出形态有三种，对应的实现微调值得明确。形态一：全输出（全排列、括号生成）——叶子处收集完整解（path[:] 拷贝）。形态二：计数（N 皇后 II、合法括号计数）——叶子处计数器加一（无需拷贝，省去拷贝的开销——本库语境的卡特兰数验证就是这么跑的）。形态三：最优解（N 皇后的「任意一个解」、数独求解）——找到第一个解即返回 True 并层层上抛（短路返回：递归函数返回 bool，True 层层传播不再探索）——「找任意解」的短路形态是回溯的效率优化（不必遍历全树）。三种形态的转换成本极低：同一个 backtrack 骨架，叶子处改三行——这也是回溯作为「通用搜索框架」的工程价值：骨架一次掌握，三种输出形态随题目要求切换。还有一个进阶形态值得一提：输出前 K 个解就停（生成器形态——Python 的 yield 把回溯变成惰性迭代器，yield path[:] 替代 result.append，调用方逐个消费——回溯 + 生成器 = 无限解空间的按需枚举，这在解数量巨大时是工程上的正确姿势）。

回溯的正确性论证模板：不重不漏怎么说

回溯解法的正确性论证有一套模板，学会它可以应对面试与评审的追问。不漏（完备性）的论证：「在每一步，所有满足约束的选择都被枚举」（全排列：每个未使用的数字都被尝试——枚举的完备性来自选择集合的完整列举）；不重（无冗余）的论证：「不同的选择序列产生不同的解」（全排列：两个不同的选择序列必然在某一位放了不同的数字——解与路径一一对应，无冗余来自「每个解只有唯一的生成路径」——这一点在子集/组合题上靠 start 下标保证、在含重复输入上靠排序加同层剪枝保证）。论证的实战话术：「枚举的完备性：每一层我都遍历了所有合法候选；解的唯一路径：每个解由唯一的决策序列生成，因此恰好被生成一次」——把这两句熟练说出，回溯题的正确性追问就基本到头了。进阶的追问方向只剩「剪枝的正确性」（剪枝会不会剪掉解？——剪枝条件的语义证明：被剪的分支不可能包含合法解——本库《N 皇后》的约束检查、本篇的 used 剪枝都满足这个要求）。

回溯的效率实测：n=10 的全排列要多久

回溯的效率值得用实测数字校准直觉。全排列的实测（Python 参考）：n=8 的 40320 个排列，纯回溯生成约几十毫秒；n=10 的 3628800 个排列，数秒——每多一个 n，时间乘以 n（阶乘的残忍）。实测带来的规模感：回溯的「可用规模」红线在 n≈12-15（解数量超过千万，输出与遍历都吃力）——红线之内回溯是王者，红线之外是灾难——这条红线也是本库《N 皇后》说「n=9 的 LeetCode 约束」的由来。实测的第二个维度：剪枝的实测收益——含重复输入的全排列 II，不加去重剪枝的版本在 [1,1,2,2] 上生成 24 个排列（其中 6 个有效），加了同层剪枝只生成 6 个——剪枝砍掉的无效分支，在实测里就是「秒级 vs 毫秒级」的差距。给学习者的校准建议：对自己写的回溯跑一次计时（time.perf_counter 包住），拿实测数字建立「我的回溯能吃多大的 n」的体感——体感数字比复杂度记号更能在现场救你。

回溯的「决策树剪枝」的通用原则：什么时候可以剪、怎么剪

回溯的剪枝有一个通用的判断框架。可以剪的两种情况：约束剪枝（当前选择违反了题目约束——不满足则后续全不满足，可以整棵子树砍掉）；最优性剪枝（当前分支的最好结果也不可能超过已知最优——通常用于优化问题）。不可以剪的情况：仅仅因为「直觉上不太可能有好解」——直觉不是剪枝的依据，约束和数学上界才是。剪枝的原则可以总结为：剪枝条件必须是「逻辑上可以证明被剪分支不包含合法解或更优解」——任何「感觉上可以」的剪枝都是 bug 的温床。实践中最好的验证方式是用暴力解做对拍——如果加了剪枝后结果变了，说明剪枝条件有 bug。

回溯与暴力枚举的关系：不是替代，是结构化

一个容易产生的误解：回溯是暴力枚举的优化版。精确的说法是：回溯是结构化的暴力枚举——暴力枚举生成所有候选然后过滤（本库括号篇的生成再过滤），回溯在生成的过程中用约束提前剪枝。两者的解集相同，但回溯的搜索空间被剪枝压缩。更精确的理解：回溯 = DFS + 约束剪枝 + 状态撤销——三个组件缺一不可：DFS 决定遍历顺序、约束剪枝决定走不走、状态撤销保证遍历的完备性。三个组件的区分训练，是回溯从背模板到写任何约束搜索题的关键。

小结

这篇收成四条：回溯骨架三步——选择、递归、撤销，撤销与选择严格对称；存结果必须拷贝 path 快照（path[:]），引用 bug 是回溯第一课的著名陷阱；回溯的复杂度由解的数量决定，考的是不重不漏的正确性；排列树用 used 数组（顺序有意义），子集树用 start 下标（顺序无意义），输入含重复时的「排序 + 同层跳过」是通用去重模式。回溯系列的路线图：全排列（本篇）→ 括号生成（带约束的生成）→ N 皇后（带剪枝的棋盘）——难度递增，骨架不变。

参考资料

• LeetCode 46. Permutations —— 题目与官方题解；LeetCode 47（含重复）为去重续作
• 本库前篇：《LeetCode 22. 括号生成》《LeetCode 51. N 皇后》—— 回溯系列的后续
• LeetCode 78. 子集、77. 组合 —— 子集树的同族题