1. 全排列题目的本质以及为什么它这么经典我在刷题过程中发现一个现象只要聊到回溯算法几乎所有的教材、题解、课程都会把“全排列”当作第一个案例来讲。原因很简单全排列这道题LeetCode 46恰好把回溯算法的三个核心要素全部囊括了——选择、递归、撤销选择。把这道题吃透后面遇到组合、子集、切割、棋盘类问题基本都是一通百通。先看题目要什么给定一个不含重复数字的数组nums返回所有可能的全排列。比如nums [1,2,3]输出必须是[1,2,3]、[1,3,2]、[2,1,3]、[2,3,1]、[3,1,2]、[3,2,1]一共3! 6种。这里有个关键点容易被新手忽略全排列结果的顺序不重要但每个排列内部元素的相对顺序必须正确且任何两个排列不能重复。换句话说[1,2,3]和[3,2,1]是两个不同的结果不能因为“组成元素相同”就合并。从数学上看全排列问题的结果数量是n!也就是阶乘级别。这个性质直接决定了算法设计的天花板——你不可能用多项式时间的算法去解决它必须接受“暴力搜索”这个现实。既然是暴力搜索那我们要做的就是让搜索过程尽量清晰、无重复、无遗漏。回溯算法就是为此而生的。我个人的建议是不要急着看题解先自己画一遍“选择树”。把第一个位置能放哪些数、第二个位置能放哪些数全画出来你会发现规律的。后面的原理拆解本质上都是基于这棵树。1.1 从“暴力枚举”到“回溯搜索”的思维跃迁很多同学第一反应是这题不是很简单吗多重循环嵌套不就行了但如果nums的长度是动态的呢题目里数组长度是输入的你不能写死的3层循环。即便你写n层循环代码的可读性和可维护性也是灾难级别的。回溯算法的解决思路是把问题看成一个多阶段决策过程第1步确定第一个元素是谁第2步确定第二个元素是谁……每一步的选择会限制后面的选择空间。当某一步发现“前面已经选过的不能再选”时就回退到上一步换一个选择继续尝试。这个“回退”动作就是“回溯”名字的由来。它本质上是一种深度优先搜索DFS但比纯 DFS 多了一个关键操作状态重置也就是把刚才做出的选择撤销掉让现场恢复到决策前的状态这样才能在同一个节点上尝试不同的分支。1.2 全排列为什么最适合用来理解“递归树的剪枝”递归树里从根节点到叶子节点的每一条路径都对应着一个完整的排列。但裸的 DFS 会把“已经选过的元素”再次选上所以我们需要用某种机制来排除这些选项。这个排除机制在“组合问题”里常靠“起始下标”实现在“排列问题”里必须靠“used 数组”或者“交换法”实现。原因很直观排列关注顺序每个位置都可以选任意一个“还没用过”的元素而不是只能选“下标比当前位置大”的元素。我记得当年自己第一次写的时候试图用组合题的startIndex思路去解全排列结果要么结果缺一半要么就是重复。后来才明白排列题和组合题在“选择范围”的定义上有着根本差异。这个感悟很重要建议你也停下来想一想。2. 回溯算法的核心原理以及状态重置到底重置了什么在开始写代码之前用文字把回溯的过程描述一遍维护一个path表示当前已经确定的排列前缀。维护一个used布尔数组used[i] true表示nums[i]已经被使用本轮不能再选。当path.length nums.length时说明已经得到一个完整排列把它加入答案。否则遍历nums的每个元素只要used[i] false就尝试选它标记used[i] true把元素加入path递归到下一层递归返回后撤销刚才的操作used[i] falsepath弹出最后一个元素继续尝试下一个未被使用的元素。这个流程里最容易出错的就是“撤销”这一步。很多人写回溯代码时递归函数末尾忘记重置used或者把path.pop()写错位置导致结果各种灵异现象。我后文会专门列一个排查清单这里先把原理说清楚。2.1 回溯与递归的关系一张图理解“递”和“归”递归分为两个阶段递向下深入和归回溯返回。回溯算法就是在递归的“归”阶段做文章。普通 DFS 的“归”只是返回而回溯的“归”还包含“清理现场”这个额外动作。如果你看源码或者自己调试会发现回溯代码的模式几乎千篇一律def backtrack(path, used): if len(path) len(nums): res.append(path[:]) # 注意这里要 copy return for i in range(len(nums)): if used[i]: continue # 做选择 used[i] True path.append(nums[i]) # 递归 backtrack(path, used) # 撤销选择 path.pop() used[i] False原理层面的精髓就一句话对同一个节点来说它通过 for 循环不断切换“选择分支”每个分支尝试完必须还原状态否则下一个分支会带着上一个分支的残留信息去尝试结果必然错误。2.2 为什么用used数组而不是直接判断in path有的同学会想判断元素是否已经用过直接if nums[i] in path不就行了确实能跑但代价不同。path是一个列表in操作是O(k)复杂度k是当前排列前缀的长度。在搜索整体复杂度为O(n!)的前提下多这个O(k)会影响整体常数但更关键的是——列表的in判断依赖元素值而全排列定义中元素值不重复所以这里没问题但如果题目改成“可重复元素的全排列”in path的判断方式就会直接导致严重的重复结果。我个人的习惯是一律使用used数组不管是简单版本还是带重复约束的进阶版本。这样代码的扩展性更好从“无重复全排列”升级到“有重复全排列”的时候只需加 3 行代码。2.3 状态重置的两个动作必须成对出现很多刚开始刷题的朋友会问“为什么path.append之后必须马上path.pop这个pop写在递归函数外面可以吗”答案是必须在本次尝试结束后、下一次尝试开始前完成撤销。我常用一个生活类比来解释你在一张白纸上写字写完一个字发现这个路线不对想换一种写法那你得先把原来的字擦掉再写新的不然两种墨迹叠在一起就乱了套。path.pop()就是“擦掉刚写的字”used[i] False就是“把这个位置的笔还给笔筒”两个动作缺一不可。3. 代码实现与核心细节python/java 双版本手把手实战原理讲再多不如亲手写一遍。这里我用 Python 和 Java 各写一个版本并详细解释每一行的意图。Python 版本适合快速验证思路Java 版本适合追求性能和工程化阅读。3.1 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 backtrack(): # 终止条件已经选满了 n 个元素 if len(path) n: res.append(path[:]) # 必须用切片生成一个副本 return for i in range(n): if used[i]: continue # 做选择 used[i] True path.append(nums[i]) # 递归进入下一层 backtrack() # 撤销选择 path.pop() used[i] False backtrack() return res几个细节我重点强调一下第一res.append(path[:])必须用切片。如果你直接res.append(path)把path这个对象本身添加进结果那么后续递归中path.pop()会同步修改已经放进res里的列表。最后你会发现res里全是同一个[]。这就是经典的“引用传递陷阱”几乎所有初学者都会踩一次。第二终止条件里不要用nums[:]之类的操作来判断长度直接len(path) n最清晰性能也最好。第三for i in range(n)每次都是从 0 开始遍历所有元素靠used来跳过已选的元素。这正是排列问题和组合问题在代码上的核心差异。3.2 Java 版本使用LinkedList和boolean[]class Solution { public ListListInteger permute(int[] nums) { ListListInteger res new ArrayList(); if (nums null || nums.length 0) { return res; } boolean[] used new boolean[nums.length]; DequeInteger path new ArrayDeque(); dfs(nums, nums.length, path, used, res); return res; } private void dfs(int[] nums, int len, DequeInteger path, boolean[] used, ListListInteger res) { if (path.size() len) { // 这里也需要拷贝 res.add(new ArrayList(path)); return; } for (int i 0; i len; i) { if (used[i]) { continue; } used[i] true; path.addLast(nums[i]); dfs(nums, len, path, used, res); path.removeLast(); used[i] false; } } }Java 版本里有几个和 Python 版本等价但写法不同的地方我说一下我的选型理由使用Deque双端队列而不是ArrayList来模拟栈操作。removeLast()是O(1)的ArrayList的remove(index)是O(n)的要移动元素逻辑上虽然都能用但Deque更贴近“栈”这个语义代码也更干净。new ArrayList(path)相当于 Python 的path[:]同样是做拷贝防止引用串改。used数组在 Java 里默认初始化全是false不用手动赋值很方便。3.3 另一种经典解法原地交换法除了used数组还有一种非常优雅的解法——交换法。思路是对于当前位置start把nums[start]和nums[i]i start交换然后递归处理start 1递归返回后再换回来恢复现场。class Solution: def permute(self, nums: List[int]) - List[List[int]]: n len(nums) res [] def backtrack(start): if start n: res.append(nums[:]) return for i in range(start, n): nums[start], nums[i] nums[i], nums[start] backtrack(start 1) nums[start], nums[i] nums[i], nums[start] backtrack(0) return res交换法的优点是不需要额外维护used数组节省了空间。缺点是它会原地修改nums对理解“状态重置”的要求更高初学阶段容易把自己绕晕。我的建议是先用used数组版本把逻辑理清楚再回头研究交换法这样能加深对回溯本质的理解又不至于一开始就迷失在交换细节里。4. 复杂度分析以及为什么全排列注定无法更优关于复杂度很多题解直接给结论时间复杂度O(n * n!)空间复杂度O(n)。但为什么是这个数很多同学并不理解。我拆开细说。4.1 时间复杂度的精确推导搜索树的节点数或者说叶子数是n!。每个叶子节点代表一个完整排列。但中间节点也要计算时间第 1 层有n个选择分支第 2 层每个节点有n-1个选择分支……所以整棵树的节点总数大约是1 n n*(n-1) n*(n-1)*(n-2) ... n!这是一个阶乘级别的求和最高阶项就是n!准确来说是e * n!级别的常数倍。而每一层递归里for循环需要遍历n次来判断used所以整体可以抓主要矛盾每个递归调用点需要 O(n) 的时间来扫描可用节点总调用次数约 O(n!)因此总时间复杂度是 O(n * n!)。如果你用交换法for循环的扫描区间会随层数递减总扫描次数会小一些但复杂度级别依然是O(n * n!)。这点不必纠结面试里能说清这个量级就够了。4.2 空间复杂度递归的深度是n递归栈的最高层数等于数组长度path最长就是nused数组也是n所以额外空间是O(n)。这里不计算res这个输出占用的空间因为它是题目要求返回的结果属于“必要输出空间”。如果面试官额外问“包含结果的空间呢”那就是O(n * n!)因为总共有n!个排列每个排列长度n。4.3 为什么没有更高效的算法全排列的输出规模本身就是n!这决定了任何算法都必须至少生成这么多结果。哪怕你的程序只做“把结果存进数组”这一件事也需要O(n!)时间。所以不要指望存在多项式时间的全排列算法。很多工程项目里硬枚举全排列导致超时问题往往出在“设计上就没必要枚举全部排列”而是可以通过剪枝、贪心、动态规划等手段缩小搜索空间。如果你发现自己的算法题总是 TLE第一反应不应该是“优化回溯常数”而应该问自己“我是不是根本不该枚举全部”5. 实操中的常见问题与排查技巧这部分是我个人最想分享的。因为我发现回溯算法翻来覆去就是那几个 bug如果你的代码跑错了大概率可以在下面的清单里找到原因。5.1 结果全是空列表或者全是同一个排列症状res输出的列表长度正确但每个元素都是[]或者都等于最后一次得到的排列。原因百分之百是“引用拷贝”问题。res.append(path)添加的是path这个对象的引用而不是它的快照。后续的path.pop()把元素删掉了之前添加的“结果”自然也跟着变空。解决办法所有需要保留现场快照的地方必须用path[:]Python或new ArrayList(path)Java。5.2 结果数量不足比如n3只输出 2 种排列症状该有的排列总是缺而且缺得很规律。原因很可能是你用了类似startIndex的思路或者交换法里交换范围写错。比如for i in range(start, n)写成了for i in range(start 1, n)第一个元素永远固定不动自然就少了(n-1)!种结果。解决办法检查你的循环起点。排列问题里每个位置可以选择“任意未使用的元素”所以要么用used数组并从头遍历要么用交换法且i从start开始。5.3 出现重复排列症状结果不唯一同一个排列出现多次。原因在基础版不含重复数字的全排列里出现重复排列的根源往往是used数组的重置时机错乱或者递归函数里对nums进行了修改但没恢复原状。具体场景比如交换法里递归返回后忘记交换回来或者used[i]的位置标错导致同一层里允许重复使用同一个元素。解决办法先在纸上画出递归树对照代码逐层推演。还可以在递归函数入口处print(path)观察状态变化很快就能定位。5.4 递归栈溢出症状RecursionErrorPython或StackOverflowErrorJava。原因n太大。注意n20时20!是一个天文数字约 2.4 亿亿任何机器都不可能枚举完。LeetCode 给出的数据范围通常是n 6或n 8这是合理的。如果你私底下尝试n15TLE 或溢出是正常现象。解决办法不要为难自己的电脑。数据量大的时候应该考虑别的算法或者接受“这题本来就不该用回溯解”的事实。5.5 常见问题速查表现象直接原因解决方案结果为[[],[],[]]添加了path引用而非副本用path[:]或new ArrayList(path)结果数量少一半循环起点错误固定了某个位置检查for循环的起点排列题通常从0或start开始结果出现重复状态未完全重置或 used 逻辑写错逐层打印 path对照递归树排查内存爆掉n太大输出规模超出合理范围调整数据规模或换非枚举思路递归死循环状态永不满足终止条件确认终止条件是否可达used是否最终全为true这五个问题基本覆盖了我在刷题群里见到的 95% 的求助帖。6. 从全排列出发延展到排列组合家族与 LeetCode 变种题全排列LeetCode 46只是整个“回溯算法家族”的一个起点。刷完这道题强烈建议立刻做它的几个变种这样才能把知识缝合成一张网。6.1 有重复元素的全排列LeetCode 47题目变成nums可能包含重复数字返回不重复的全排列。比如nums [1,1,2]结果不能有多个[1,1,2]。解决方案是在原回溯基础上加一个“同层去重”剪枝。核心逻辑是在同一层for循环里如果一个元素和上一个元素相等并且上一个元素刚被撤销used[i-1] false就跳过当前元素。nums.sort() # 必须先排序让重复元素相邻 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-1] false意味着nums[i-1]在上一层已经被用过并且已经撤销了当前层又轮到了相同的值如果再选就会产生以“相同前缀”开头的重复分支。这个剪枝技巧也是 “组合总和 II” 等题目的核心。6.2 组合问题LeetCode 77与子集问题LeetCode 78全排列选“所有位置可以任意选未使用的元素”而组合是“从 n 个元素中选 k 个顺序无关”。组合使用startIndex控制选择范围避免出现[1,2]和[2,1]这种重复结果。子集问题[1,2,3]的所有子集本质上就是“长度从 0 到 n 的所有组合”。理解了全排列和组合的区别子集就是顺手的事。6.3 下一个排列LeetCode 31这道题和回溯没有关系它要求你实现“字典序的下一个排列”。它考察的是对排列顺序规律的掌握完全属于另一类技巧。但如果全排列刷得足够多你会对排列的顺序性质有更好的直觉写这个题会顺手很多。6.4 全排列问题在生产场景中的真实用途很多同学会问全排列除了刷题到底有什么用我说几个我实际接触过的场景权限系统中针对一组角色的所有分配方式枚举。任务调度的顺序枚举比如“3 台机器处理 5 个任务的先后顺序”。数据脱敏规则的排列组合测试用itertools.permutationsPython 自带来穷举小规模的组合情况。小规模搜索题的暴力求解比如数独、八皇后本质都是回溯 剪枝的变体。当然生产环境里若数据量变大阶乘级枚举很快就会暴毙所以这类代码通常只用于离线计算或数据量极小n 8的场景。这反而是它作为“基础算法教学题”的另一种价值——让你永远不会忘记阶乘级别到底有多恐怖。6.5 我的实战心得刷全排列一定要做三件事第一件事手动调试一次递归过程。不要只跑通就完事在backtrack的入口和出口各加一个print打印path和used的状态亲眼看看“回溯”是怎么发生的。这一步比看十篇题解都有效。第二件事不看模板从零手写三遍。间隔一天、三天、一周各写一次三次以后你会发现肌肉记忆已经形成。面试时能在 5 分钟内无 bug 写出全排列基本就是回溯算法过关了。第三件事把交换法也写一遍。虽然平时我更推荐used数组法但交换法里“交换—递归—换回”的模式对理解“状态重置”有不可替代的启发。从 LeetCode 46 这道题出发你能触达的回溯知识点其实是一个庞大的家族组合、分割、子集、棋盘、图论中的哈密顿路径……但万变不离其宗的就是 “做选择—递归—撤销选择”这个黄金三角。把全排列吃透你就已经在这个家族里站稳了脚跟。
