企业官网建设流程全解析

做算法题做到“全排列”这道题，算是刷题路上的一个分水岭。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! 是 720，7! 是 5040，10! 是 362 万，12! 直接到了 4.79 亿。这增长速度比指数还恐怖，就算每个排列只占很少的存储，也撑不住。题目把 n 限制在个位级别不是随便定的，是在告诉你：这道题的复杂度本质上是阶乘级，能跑完就已经是极限了。

1.2 为什么普通循环在这里失效

很多新手第一反应是：数组长度是几，就写几层嵌套 for 不就行了？三个数 [1,2,3]，三层循环每个位置选一个数，再用 if 排除重复，确实能出结果。可问题是，n 是运行期才知道的输入。n=3 你写三层循环，n=6 你要写六层，n=10 呢？你不可能在写代码的时候动态生成 n 层嵌套 for。

就算硬用计数器模拟进位，代码也会变成一个很难读懂的怪物。所以问题的本质是：我们需要一种“循环层数不固定”的遍历方式。递归恰好提供了这个能力——每一层递归相当于一层循环，递归的深度就是 n，于是“n 层嵌套循环”就变成了“深度为 n 的递归”，这本质上就是深度优先搜索（DFS）在决策树上的遍历。

2. 回溯算法：解决排列问题的默认武器

2.1 回溯的核心套路：选择、递归、撤销

回溯算法翻译成人话就是“走迷宫”：往前走，发现此路不通（或者已经走到终点），就退回来换一条路再走。全排列可以这样想：面前有 n 个数字，我要把它们依次填进 n 个坑位，每个数字只能用一次，填满 n 个坑就得到一个排列。

每填一个坑，我要从“还没用过的数字”里挑一个。挑完进入下一层，填下一个坑。填满之后记录结果，然后把最后填的数字“释放”出来，换一个数字再试。“释放”这一步就是撤销，是整个回溯里最容易被忽略、也最容易出错的动作。

对应到代码，就是固定的三件套：

1. 选择：把当前数字标记为已使用，加入 path。
2. 递归：继续填下一个位置。
3. 撤销：把数字从 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。这棵树肉眼可见地膨胀：n=4 时叶子变成 24 个，n=6 时变成 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 交换，然后递归处理 index+1，处理完再交换回来。交换法不需要 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 List<List<Integer>> permute(int[] nums) { List<List<Integer>> res = new ArrayList<>(); List<Integer> path = new ArrayList<>(); boolean[] used = new boolean[nums.length]; dfs(nums, used, path, res); return res; } private void dfs(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> 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 循环 i=0，nums[0]=1 未使用，于是 used[0]=True，path=[1]，递归进入第二层。第二层里 i=0 已经被 used 跳过，i=1 选 2，path=[1,2]，再进入第三层。第三层只能选 3，path=[1,2,3]，len(path)==3，记录 [1,2,3]，返回。回到第三层的 for 循环，i 已经遍历完，函数自然结束，返回第二层。第二层刚才是选了 i=1，现在撤销：path.pop() 变回 [1]，used[1]=False，继续 for，i=2 选 3，path=[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 阶乘有多爆炸：为什么题目只敢给 n=6

我在 1.1 里提过 12! = 4.79 亿，这里再展开算一遍账。假设一台普通机器每秒能处理约 10^8 次基本操作，生成并记录 4.79 亿个排列，哪怕每个排列只算一次拷贝操作，也要好几秒；再加上每个排列长度 12 的复制，实际耗时轻松上几十秒。所以 LeetCode 宁可把 n 限制成 6，也不给你一个“理论上正确但永远跑不完”的测试点，这是在维护题目的可评测性。

这个认知也提醒我们：所有输出全排列的算法题，n 都大不了。真正遇到大量排列需求的场景，比如给定 n=20，千万别想着枚举，那是 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 的引用放进 res，path 后续一变，已经“加入”结果的那个列表也跟着变。最终 res 里所有元素都会指向同一个列表，而且这个列表在递归结束后会回到空状态。

正确做法是 res.append(path[:])，或 res.append(list(path))。Java 同理，必须 res.add(new ArrayList<>(path))。这个坑看着小，但我在帮别人 review 代码时几乎每周都能遇到一次。记住一个原则：凡是把“会继续变化的可变对象”存进结果集，都必须拷贝。

5.3 递归深度和性能的权衡，别等出问题才重视

Python 默认递归深度限制是 1000，全排列 n 最多 6，完全不用担心。但如果哪天你把这段代码拿去处理 n=8 或者更深的场景，就要注意递归栈和耗时了。另一个容易被忽略的性能点是 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[i+1] 的位置；在 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 的时候，直接枚举所有排列然后按约束筛选，比上一套复杂算法简单可靠得多，这是很多人容易忽略的一条实用路径。

最后分享一个我用了很久的习惯。每次遇到不熟悉的回溯题，我不急着写代码，而是先在草稿纸上画出决策树的前两层，标清楚每个节点的状态是什么，哪些分支会因为限制条件被剪掉。画完再写代码，思路会清晰一个档次。全排列这道题是训练这个习惯最好的起点——它结构简单，画出来的树优美对称，非常适合用来建立“递归即树的遍历”这个心智模型。把全排列吃透之后，你会发现后面那些带限制条件的回溯题，无非是在这棵树上多做几次剪枝罢了。