全排列与回溯算法：从LeetCode 46到面试变体的深度解析

做算法题做到“全排列”这道题算是刷题路上的一个分水岭。LeetCode 46 题面很短给你一个不含重复数字的数组比如 [1,2,3]要求返回所有可能的排列也就是 [1,2,3]、[1,3,2]、[2,1,3]、[2,3,1]、[3,1,2]、[3,2,1] 这六个结果顺序不限。题是好懂的可就这六个结果难住过不少人。我见过太多人在这个题上卡住不是不会写 for 循环而是第一次直面“递归 回溯”这套组合拳时脑子里没有那张决策树的图。这篇文章写给三类人刚刷题的新手想彻底吃透回溯模板面试前想快速复习排列问题的进阶选手以及被全排列各种变体题反复折磨、想建立系统框架的老手。我会从暴力解法为什么走不通讲起把回溯原理、两种主流代码写法、复杂度推导、常见 bug 和面试变体一次讲完代码以 Python 为主关键地方补 Java 版本。1. 题目理解全排列到底难在哪1.1 先看清题面两个约束条件决定了解法方向LeetCode 46 原题描述非常简单给定一个不含重复数字的数组 nums返回其所有可能的全排列。输出顺序任意。约束条件有两个点值得注意一是 nums 里的元素互不相同二是数组长度通常被限制在个位数级别。第一点意味着我们暂时不用考虑“重复元素造成重复排列”的剪枝问题。等到了全排列 II第 47 题数组里会出现重复数字那时候 [1,1,2] 这类输入要求你输出 [1,1,2]、[1,2,1]、[2,1,1] 三个结果而不是六个处理方式就得加排序和剪枝这个我放在后面专门讲。第二点更关键。全排列的总数是 n!6! 是 7207! 是 504010! 是 362 万12! 直接到了 4.79 亿。这增长速度比指数还恐怖就算每个排列只占很少的存储也撑不住。题目把 n 限制在个位级别不是随便定的是在告诉你这道题的复杂度本质上是阶乘级能跑完就已经是极限了。1.2 为什么普通循环在这里失效很多新手第一反应是数组长度是几就写几层嵌套 for 不就行了三个数 [1,2,3]三层循环每个位置选一个数再用 if 排除重复确实能出结果。可问题是n 是运行期才知道的输入。n3 你写三层循环n6 你要写六层n10 呢你不可能在写代码的时候动态生成 n 层嵌套 for。就算硬用计数器模拟进位代码也会变成一个很难读懂的怪物。所以问题的本质是我们需要一种“循环层数不固定”的遍历方式。递归恰好提供了这个能力——每一层递归相当于一层循环递归的深度就是 n于是“n 层嵌套循环”就变成了“深度为 n 的递归”这本质上就是深度优先搜索DFS在决策树上的遍历。2. 回溯算法解决排列问题的默认武器2.1 回溯的核心套路选择、递归、撤销回溯算法翻译成人话就是“走迷宫”往前走发现此路不通或者已经走到终点就退回来换一条路再走。全排列可以这样想面前有 n 个数字我要把它们依次填进 n 个坑位每个数字只能用一次填满 n 个坑就得到一个排列。每填一个坑我要从“还没用过的数字”里挑一个。挑完进入下一层填下一个坑。填满之后记录结果然后把最后填的数字“释放”出来换一个数字再试。“释放”这一步就是撤销是整个回溯里最容易被忽略、也最容易出错的动作。对应到代码就是固定的三件套选择把当前数字标记为已使用加入 path。递归继续填下一个位置。撤销把数字从 path 移出取消已使用标记。这个模板不仅适用于全排列。子集78 题、组合77 题、组合总和39 题、分割回文串131 题、N 皇后51 题全都长着同一张脸。你把全排列这个模板吃透等于给一大类回溯题打了底子。2.2 画一棵决策树递归过程一目了然学回溯一定要建立决策树的概念。拿 [1,2,3] 举例整个搜索过程可以画成这样一棵树[] / | \ [1] [2] [3] / \ / \ / \ [1,2] [1,3] [2,1] [2,3] [3,1] [3,2] | | | | | | [1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]根节点代表一个空排列第一层决定第一个坑位填谁第二层决定第二个坑位填谁第三层填满就是叶子节点也就是一个完整排列。树的每一层都对应递归的一次进入叶子节点的数量正好是 n! 6。这棵树肉眼可见地膨胀n4 时叶子变成 24 个n6 时变成 720 个。画这张图最大的好处是你能清楚地看到“回溯”发生在哪里从叶子 [1,2,3] 退回到 [1,2]再换一条分支变成 [1,3,2]从 [1,3,2] 退回 [1,3]再退到 [1]然后向右换到 [2] 开头的分支。递归调用栈的压栈、出栈跟树的深入、回退完全对应。2.3 两种主流的代码思路到底该学哪个全排列的实现大致分两派。第一派是“显式维护已用集合”的思路开一个 path 列表存放当前排列开一个 used 布尔数组标记哪些数字已经用过每层递归遍历整个 nums遇到已用的跳过没用过的就选它。这套写法思路直观也最容易迁移到组合、子集问题缺点是额外多一个 used 数组并且每层都要完整遍历 nums。第二派是“交换法”直接在原数组上操作把当前要固定的位置 index 和后面某个位置 i 交换然后递归处理 index1处理完再交换回来。交换法不需要 used 数组代码更短但理解成本稍高而且在处理重复元素时需要额外注意剪枝逻辑不太适合直接迁移到组合类问题。选哪派取决于场景。我个人建议新手先把第一派学扎实因为它的语义最清晰交换法可以作为进阶能力面试时偶尔用来展示你对递归的理解深度。3. 完整代码实现两种写法一次讲清楚3.1 used数组 path最容易上手的写法先上 Python 最经典的版本from typing import List class Solution: def permute(self, nums: List[int]) - List[List[int]]: n len(nums) used [False] * n path [] res [] def dfs(): # 递归终止path 已经填满 n 个数字 if len(path) n: res.append(path[:]) # 关键必须拷贝不能直接 append(path) return # 每一层都从 nums 里挑一个没被用过的数字 for i in range(n): if used[i]: continue # 选择 used[i] True path.append(nums[i]) # 递归下一层 dfs() # 撤销 path.pop() used[i] False dfs() return res这段代码里浓缩了回溯的所有精髓。dfs() 函数每被调用一次就代表我们站在决策树的某一层正在决定 path 的下一个元素。len(path) n 时意味着从根到一个叶子节点的路径已经完整把 path 的拷贝加入结果。如果没填满就遍历所有候选数字选一个没用的继续深入。有一个点必须强调res.append(path[:]) 里的 [:] 是深拷贝。如果写成 res.append(path)后面 path.pop() 时已经加入 res 的那个列表也会跟着变最终结果会变成一堆相同的空列表。这是回溯题最经典的坑之一我后面还会详细讲。3.2 Java 版本特别提醒引用拷贝Java 的写法和 Python 是对应的只是集合操作的 API 不同class Solution { public ListListInteger permute(int[] nums) { ListListInteger res new ArrayList(); ListInteger path new ArrayList(); boolean[] used new boolean[nums.length]; dfs(nums, used, path, res); return res; } private void dfs(int[] nums, boolean[] used, ListInteger path, ListListInteger res) { if (path.size() nums.length) { res.add(new ArrayList(path)); return; } for (int i 0; i nums.length; i) { if (used[i]) { continue; } used[i] true; path.add(nums[i]); dfs(nums, used, path, res); path.remove(path.size() - 1); used[i] false; } } }Java 里的 res.add(new ArrayList(path)) 和 Python 的 path[:] 一样都是拷贝当前 path 的副本而不是把引用本身存进去。Java 新手经常忘掉 new ArrayList(path) 这一层包装导致最后 res 里全是同一个 path 的最终状态。3.3 交换法省掉 used 数组的精简方案再说第二种思路。既然每个数字最终都要被固定到每个位置一次那不如直接在原数组上玩换位游戏from typing import List class Solution: def permute(self, nums: List[int]) - List[List[int]]: res [] n len(nums) def dfs(index: int): # index 表示当前要固定第 index 个位置 if index n: res.append(nums[:]) return for i in range(index, n): # 把 nums[i] 换到第 index 位 nums[index], nums[i] nums[i], nums[index] # 固定第 index 位继续排后面的位置 dfs(index 1) # 换回来恢复现场 nums[index], nums[i] nums[i], nums[index] dfs(0) return res这段代码的核心是dfs(index) 表示第 index 位之前的位置已经固定接下来要把 nums[index] 到 nums[n-1] 之间的数字逐个放到第 index 位然后递归处理剩余位置。i 从 index 开始包含了“当前位置保持原样”的情况这对应某个数字天然就在该位置的排列。交换法省掉了 used 数组也不需要 path空间上更省但它直接修改了原数组res.append(nums[:]) 里的 [:] 仍然不能少否则存进去的引用会随着后续交换不断变化。还有一点要注意交换法在处理含重复数字的全排列 II 时剪枝条件比 used 法难写所以如果目标是把变体题也一网打尽还是优先掌握 used 法。3.4 手动走一遍 [1,2,3]看清递归每一帧纸上得来终觉浅。我用 used 法手动模拟一下 [1,2,3] 的前几个分支帮你建立递归的“帧”的感觉。最开始 used[F,F,F]path[]进入 dfs()。for 循环 i0nums[0]1 未使用于是 used[0]Truepath[1]递归进入第二层。第二层里 i0 已经被 used 跳过i1 选 2path[1,2]再进入第三层。第三层只能选 3path[1,2,3]len(path)3记录 [1,2,3]返回。回到第三层的 for 循环i 已经遍历完函数自然结束返回第二层。第二层刚才是选了 i1现在撤销path.pop() 变回 [1]used[1]False继续 fori2 选 3path[1,3]……后面以此类推。每一层返回后都会立刻恢复现场这正是回溯能遍历所有组合而不重不漏的原因。手动走一遍之后你会意识到递归里所谓的“状态”完全是由 path 和 used 共同刻画的撤销操作其实就是把状态精确还原到递归进入之前。只要这个还原是严格的枚举就一定是完整的。4. 复杂度分析与面试中的延伸提问4.1 时间复杂度O(n * n!) 是怎么推出来的先说结论全排列的时间复杂度是 O(n * n!)比很多人随口说的 O(n!) 更精确。推导分成两部分。第一部分n 个不同元素的全排列总数是 n!这个不用多说。第二部分每得到一个排列我们都做了一次 path[:] 拷贝把长度 n 的列表复制到结果里耗时 O(n)。所以总时间 排列个数 × 每个排列被记录的时间 O(n * n!)。很多人会忽略一个细节除了最终的拷贝递归过程中每层的 for 循环本身也有开销。used 法里每个节点都会遍历 nums 找可选项决策树的节点总数是 n! 量级准确说是这棵树从根到第 n 层所有节点加起来每一层对 n 的遍历又要乘一个常数因子。不过这些常数不会改变阶乘主导的结论大 O 上依然是 O(n * n!)。交换法因为不额外拷贝 path记录结果时也要拷贝一次 nums同样逃不掉这个 O(n)。4.2 空间复杂度调用栈、辅助数组、结果集分开算空间上要分三块算。第一块是递归调用栈最深会同时调用 n 层每层是 O(1) 的局部状态所以栈深 O(n)。第二块是辅助结构used 数组 O(n)path 列表 O(n)加起来 O(n)。第三块是结果集 res它要存 n! 个排列每个排列长度 n所以是 O(n * n!)。面试里如果你写到“空间复杂度 O(n)”严格来说是对的但前提是别把输出结果算进去。通常我们会区分“额外空间”和“输出空间”额外空间是 O(n)输出空间 O(n * n!) 是题目要求的必然开销。面试官问空间复杂度一般是问额外空间你回答 O(n) 并补充一句“不算结果集”就稳了。4.3 阶乘有多爆炸为什么题目只敢给 n6我在 1.1 里提过 12! 4.79 亿这里再展开算一遍账。假设一台普通机器每秒能处理约 10^8 次基本操作生成并记录 4.79 亿个排列哪怕每个排列只算一次拷贝操作也要好几秒再加上每个排列长度 12 的复制实际耗时轻松上几十秒。所以 LeetCode 宁可把 n 限制成 6也不给你一个“理论上正确但永远跑不完”的测试点这是在维护题目的可评测性。这个认知也提醒我们所有输出全排列的算法题n 都大不了。真正遇到大量排列需求的场景比如给定 n20千万别想着枚举那是 20!宇宙毁灭都算不完。现实方案是换思路用“下一个排列”按字典序增量生成或者用启发式算法求近似解。5. 常见问题与调试技巧实录5.1 经典 bug撤销操作写漏或写错顺序我自己刚开始学回溯时最常犯的错就是忘记撤销。path.append 之后直接递归递归完不 pop导致 path 越滚越长最终结果全是同一组数字的不同截断版。还有一种更隐蔽的错撤销顺序反了。比如先 used[i]False 再 path.pop()看起来都做了但如果后面紧接着的代码对 path 状态有依赖就会出问题。建议把“撤销”固定成一组对称操作选择时做了什么撤销时就严格按照相反顺序做一遍path.append → dfs() → path.pop()used[i]True → dfs() → used[i]False。调试这类问题很简单在 dfs() 入口打印一层缩进输出当前 path跑一遍 [1,2,3]肉眼观察 path 是否在返回时被正确还原。如果某个分支结束后 path 长度没有回到分支前的状态撤销一定有问题。5.2 引用陷阱path 还是 path[:]务必分清楚这是全排列题出现频率最高的第二个坑。Python 里 res.append(path) 只是把 path 的引用放进 respath 后续一变已经“加入”结果的那个列表也跟着变。最终 res 里所有元素都会指向同一个列表而且这个列表在递归结束后会回到空状态。正确做法是 res.append(path[:])或 res.append(list(path))。Java 同理必须 res.add(new ArrayList(path))。这个坑看着小但我在帮别人 review 代码时几乎每周都能遇到一次。记住一个原则凡是把“会继续变化的可变对象”存进结果集都必须拷贝。5.3 递归深度和性能的权衡别等出问题才重视Python 默认递归深度限制是 1000全排列 n 最多 6完全不用担心。但如果哪天你把这段代码拿去处理 n8 或者更深的场景就要注意递归栈和耗时了。另一个容易被忽略的性能点是 used 法里每层都从头扫描整个 nums当 n 较大时大量时间消耗在对“已用元素”的重复判断上。实测下来如果只是为了跑通 LeetCode两种写法都是毫秒级差别可以忽略但如果要在竞赛里追求极限交换法因为省去了 used 数组和 path 的动态增删常数会更小。我不建议为了这种微优化牺牲可读性面试官更看重的是你能把回溯逻辑讲清楚。5.4 几个让代码更稳的小习惯第一个习惯是别忘了处理空数组边界。题目保证 nums 非空但写工具函数时加上 if not nums: return [] 不亏。第二个习惯是先 sort 还是后 sort全排列 I 因为元素互不相同排序不影响结果但为了后续迁到全排列 II我建议一开始就养成“先排序再回溯”的习惯。第三个习惯是尽量用局部变量传递状态不要用全局变量否则递归之间的状态污染会让你 debug 到怀疑人生。6. 从全排列出发相关题目与进阶思路6.1 全排列 II一行剪枝解决重复元素LeetCode 47 是全排列的加强版输入数组可能包含重复数字要求返回不重复的全排列。思路是在 46 题的 used 法基础上先对 nums 排序然后在每层 for 循环里加一个剪枝条件class Solution: def permuteUnique(self, nums: List[int]) - List[List[int]]: nums.sort() n len(nums) used [False] * n path [] res [] def dfs(): if len(path) n: res.append(path[:]) return for i in range(n): if used[i]: continue # 同一层跳过重复数字 if i 0 and nums[i] nums[i - 1] and not used[i - 1]: continue used[i] True path.append(nums[i]) dfs() path.pop() used[i] False dfs() return res这个剪枝的判定条件是整个 47 题的核心nums[i] nums[i-1] 表示遇到重复数字not used[i-1] 表示前一个相同数字在本层还没有被用过。为什么要求 not used[i-1]因为 used[i-1] 为 True 时说明重复数字是上一层选的当前层选它没问题属于同一个排列内部的延续只有 used[i-1] 为 False说明前一个相同数字在本层已经被尝试并回溯了当前这个再试就会产生一模一样的排列必须剪掉。理解了这行全排列 II 就没有秘密了。6.2 下一个排列不生成全排列也能操作排列LeetCode 31 不走枚举路线而是给定一个排列要求原地改成字典序的下一个排列。核心算法是三步从右往左找第一个 nums[i] nums[i1] 的位置在 i 右边找比 nums[i] 大的最小元素和 i 交换把 i 之后的区间反转成升序。如果 nums 整体是降序说明当前已经是最后一个排列直接整体反转回到第一个排列。这个算法的时间是 O(n)空间 O(1)不需要生成任何排列但用到了排列的字典序性质和全排列题形成很好的互补。你要是把 46 和 31 连着做对“排列空间是有序的”这件事会有很深的体会。6.3 排列序列用阶乘直接定位第 k 个排列LeetCode 60 问 n 个数字的第 k 个字典序排列是什么n 最多到 9。直接调全排列再取第 k 个虽然也能得到答案但 n! 量级的结果集生成太浪费。更聪明的做法是利用阶乘逐位确定def getPermutation(n: int, k: int) - str: fact [1] * (n 1) for i in range(1, n 1): fact[i] fact[i - 1] * i digits list(range(1, n 1)) k - 1 # 转成 0 索引 res [] for i in range(n, 0, -1): block fact[i - 1] # 首位固定后剩余数字的排列数 idx k // block # 当前位的数字在剩余数字中的下标 k % block res.append(str(digits.pop(idx))) return .join(res)解释一下第一位固定后后面 n-1 个数字有 (n-1)! 种排列所以每 (n-1)! 个排列共享同一个首位。用 k 除以 (n-1)! 就能定位首位是谁余数继续用于确定后续位。整个过程只需要 O(n) 次 pop 操作非常优雅。做这道题之前先吃透 46 题的“排列数量是阶乘”这个直觉理解起来会顺很多。6.4 排列思想在现实场景中的应用全排列不是只在面试题里出现。旅行商问题要枚举城市访问顺序本质上就是排列问题工厂排产、课程表编排、任务调度凡是“给一组对象安排一个顺序”的场景最朴素的做法都是枚举排列再过滤约束。还有一类测试场景你想穷举一个系统的所有输入顺序组合来验证正确性本质上也在做全排列。当然现实业务里 n 稍微大一点纯枚举就扛不住了工程上会用遗传算法、模拟退火、蚁群算法这类启发式方案去逼近最优解。但从思维训练的角度讲全排列教会你的“状态空间建模 回溯搜索”能力是理解那些高级算法的地基。我在实际项目中就经常用回溯求解一些小规模的排产问题n 不超过 8 的时候直接枚举所有排列然后按约束筛选比上一套复杂算法简单可靠得多这是很多人容易忽略的一条实用路径。最后分享一个我用了很久的习惯。每次遇到不熟悉的回溯题我不急着写代码而是先在草稿纸上画出决策树的前两层标清楚每个节点的状态是什么哪些分支会因为限制条件被剪掉。画完再写代码思路会清晰一个档次。全排列这道题是训练这个习惯最好的起点——它结构简单画出来的树优美对称非常适合用来建立“递归即树的遍历”这个心智模型。把全排列吃透之后你会发现后面那些带限制条件的回溯题无非是在这棵树上多做几次剪枝罢了。