全排列与回溯算法：从DFS到剪枝去重，彻底搞懂排列生成-平芜编程栈

全排列是个很奇妙的东西。它可能是很多人接触“回溯算法”的第一道门，也是面试里出镜率极高的常客——从最简单的“三个数字有几种排法”，到力扣上那个经典的“全排列 II”去重题，再到竞赛里各种排列相关的状态压缩、康托展开，本质上都绕不开这层核心：怎么不重不漏地把所有排列方式全部列出来。

我最早学全排列的时候，是在纸上硬列规律，后来发现老手们都在聊“回溯”、“DFS”、“剪枝”、“字典序”。这些名词看着唬人，其实拆开了就是一套“试错 + 回头”的流程。这篇文章就把这套流程彻底讲透，从暴力枚举到经典回溯，从普通全排列到带重复数字的去重版本，再到时间复杂度分析、优化思路和最容易被忽略的边界细节，一次性整理清楚。

1. 全排列到底在解什么问题

1.1 从一个最简单的问题说起

假设你有 3 张卡片，上面分别写着 1、2、3，你随手一摆，能摆出多少种不同的顺序？答案是 6 种：

1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1

如果没有卡牌，我们换一种说法：给定一个包含若干个不同元素的集合，要求输出它的所有排列方式，每个排列包含全部元素，且元素不能重复出现。

排列的定义本身很简单，公式大家也都知道：n 个不同元素的全排列数量是 n!。比如 n = 3，就是 3! = 6；n = 4，就是 4! = 24；n = 10，就是 3628800，超过三百万了。

问题是：公式能算出数量，但程序要的不是数量，而是这 n! 种排列本身。所以我们要设计一种“生成策略”，让计算机像人脑一样，有条理地把所有结果枚举出来。

1.2 为什么程序枚举排列比想象中麻烦

人脑做这件事很轻松，因为我们会“脑补”：先确定第一位，再确定第二位，最后补上剩下的。但程序不会脑补，它只懂得循环、递归、调用栈。你得把“确定第一位”这件事变成一个可重复执行的步骤。

这里藏着一个关键点：排列问题本身具有明显的递归结构。你确定第一个位置用了哪个元素之后，剩下的问题就从“对 n 个元素做全排列”变成了“对剩下的 n-1 个元素做全排列”。问题规模缩小了，但问题的性质没变——这就是典型的递归可解问题。

另一个麻烦来自状态管理。你在第 1 层选了 1，接下来递归处理 [2, 3]；处理完以后要回头试第 1 层选 2，这时你必须把之前“选过 1”这个状态撤销干净，否则后面就会出错。这个“撤销”动作，就是回溯算法里“回溯”二字的由来。

1.3 全排列的应用场景超出想象

很多人觉得全排列就是一道算法题，除了面试没别的用处。这是最典型的误解。

密码爆破与字典生成：在规则明确的前提下，全排列用于生成所有可能的字符组合方案；
路径规划与旅行商问题的暴力解法：n 个城市的访问顺序就是一个排列，暴力求解 TSP 就是枚举所有排列；
竞赛编程中的排列枚举：很多状态搜索题的第一步就是刷牙排列，然后再配合剪枝优化；
数据库查询优化：多表连接顺序其实也是排列问题；
游戏与抽卡概率计算：抽卡顺序、掉落组合等，只要涉及顺序都要用排列思路。

所以全排列不是一道孤立的“应付面试的题”，它是一系列算法的基础。把全排列想明白了，再去看 N 皇后、组合总和、括号生成这类回溯题，会发现全都是一套模板。

2. 核心思路拆解：DFS、回溯与状态重置

2.1 把排列过程“画”成一棵树

学习全排列最重要的思维转换，就是从“列表”思维切换到“树”思维。

以 1、2、3 的全排列为例，整个枚举过程可以画成下面这棵树：

第一层（根）：空序列，什么都没选；
第二层（第一个位置）：选了 1 / 选了 2 / 选了 3；
第三层（第二个位置）：在选完 1 的基础上，可以选 2 或 3；以此类推。

这棵树一共有 n 层，每往下一层就多一个元素进入结果序列。树的叶子结点（最底层）就是每一个完整排列。

DFS 就是深度优先遍历这棵树的方式：先沿着“选了 1”这条路走到头，得到完整排列 [1, 2, 3] 和 [1, 3, 2]，然后回到“选了 1”这个分支的起点，再去走“选了 2”这条路，直到整棵树全部遍历完。

2.2 回溯三要素：路径、选择列表、终止条件

任何回溯算法都可以用三个要素来描述，全排列也不例外：

路径（track）：记录已经被选中的元素顺序；
选择列表（available）：记录当前还剩哪些元素可以用；
终止条件（base case）：路径长度等于 n，说明所有元素都用完了，此时把当前路径记录下来。

回溯算法的框架是高度统一的，基本长这样：

def backtrack(路径, 选择列表): if 满足终止条件: 记录结果 return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择

这就是所谓的“回溯模板”。它不只适用于全排列，几乎适用于所有排列组合类问题。

2.3 为什么必须“撤销选择”

这是新手最容易犯的错，也是理解回溯的关键。我们看一个场景：

当前路径 = [1]，选择列表 = [2, 3]；
递归处理完之后，路径变成 [1, 2, 3]，输出；
接下来要尝试的是路径 = [1, 3]，选择列表 = [2]。

但在递归返回时，如果代码在递归前后没有做好“恢复现场”，路径就会一直停留在 [1, 2, 3]，那么你下一个尝试的起点就变成了 [1, 2, 3] 而不是 [1]，“回头”就变成了“一条道走到黑”。

撤销选择的本质，是为了保证同一个层级的多个分支之间互不污染。这就像你在笔记本上做草稿计算，每试一种情况之前，都必须把上一笔擦干净；如果不擦掉，各个分支的数据搅在一块儿，最后全乱套。

3. 经典实现：三种语言的写法与对比

3.1 基于“已选集合”的回溯写法（Python）

最常见的写法是用一个used布尔数组来标记元素是否已经被使用，配合 DFS 递归实现。

def permute(nums): res = [] n = len(nums) used = [False] * n track = [] def dfs(): if len(track) == n: res.append(track[:]) # 注意这里必须拷贝 return for i in range(n): if used[i]: continue used[i] = True track.append(nums[i]) dfs() track.pop() used[i] = False dfs() return res

这个代码的时间复杂度是 O(n × n!)，空间复杂度是 O(n)（递归栈）加上结果集本身的需要。为什么是 O(n × n!)，后面会专门讲。

3.2 基于“交换法”的实现（C++ / Java）

交换法的思路不一样：它在原数组上做交换，每次递归确定一个位置；递归到下一层时，把当前位置和后面的每个位置依次交换，这样就不需要额外的used数组了。

class Solution { public: vector<vector<int>> result; void backtrack(vector<int>& nums, int start) { if (start == nums.size()) { result.push_back(nums); return; } for (int i = start; i < nums.size(); ++i) { swap(nums[start], nums[i]); backtrack(nums, start + 1); swap(nums[start], nums[i]); // 撤销交换 } } vector<vector<int>> permute(vector<int>& nums) { backtrack(nums, 0); return result; } };

这段代码每次递归到最底层时，nums本身就是一个合法的排列，所以直接把nums压入结果。这里最需要注意的还是那两行swap：换完之后必须再换回来，否则下一次循环的起点就被污染了。

交换法的代码更简洁，不需要used数组，但它的排列生成顺序不是字典序（后面会细说）。如果你只求列出所有排列，不要求顺序，交换法更清爽；如果要求按字典序输出，用“选数法 + used 数组”更自然。

3.3 Java 版本实现：兼顾代码规范与工具类

class Solution { List<List<Integer>> res = new ArrayList<>(); boolean[] used; int n; public List<List<Integer>> permute(int[] nums) { n = nums.length; used = new boolean[n]; Deque<Integer> path = new ArrayDeque<>(); dfs(nums, path); return res; } private void dfs(int[] nums, Deque<Integer> path) { if (path.size() == n) { res.add(new ArrayList<>(path)); return; } for (int i = 0; i < n; i++) { if (!used[i]) { used[i] = true; path.addLast(nums[i]); dfs(nums, path); path.removeLast(); used[i] = false; } } } }

这里我刻意用了Deque而不是List，目的是强调“路径”这个变量在递归过程中是频繁头尾操作的，用双端队列在语义和性能上都更合适。Java 版本里一个常见的坑是直接res.add(path)，这会把同一个对象的引用加入结果集，最后所有排列都会变成同一个值。正确写法是新建一个ArrayList拷贝当前路径。

4. 进阶核心：全排列 II 的重复元素与剪枝

4.1 重复元素带来的问题

普通的全排列假设所有元素互不相同。但实际题目（比如力扣 47 题“全排列 II”）经常会给出包含重复元素的数组，比如[1, 1, 2]。

如果直接套用普通全排列的代码，会得到重复结果：

1 1 2 1 2 1 1 1 2 （重复！） 1 2 1 （重复！） 2 1 1 2 1 1 （重复！）

正确结果应该是 3 个，而不是 6 个。重复的本质原因是：两个相同的 1 被视为不同的元素进行了交换和选择，导致同一种排列被枚举了多次。

4.2 去重的两个维度：排序 + 剪枝

解决重复的经典策略分两步：

第一步：排序。把nums从小到大排序，让相同的元素相邻。这是后续剪枝的前提。

第二步：在 for 循环里剪枝。当遇到nums[i] == nums[i - 1]且前一个相同元素没有被访问过时，直接跳过当前分支。

具体的剪枝判断写法有很多种，我推荐在用used数组的框架里写成这样：

def permuteUnique(nums): nums.sort() res = [] n = len(nums) used = [False] * n track = [] def dfs(): if len(track) == n: res.append(track[:]) 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 track.append(nums[i]) dfs() track.pop() used[i] = False dfs() return res

这里的关键是not used[i - 1]这个条件。很多人会写成used[i - 1] == True，这得到的结果也能去重，但面试时最好能说清楚两者的区别。

4.3 剪枝条件 used[i-1] 到底该取 True 还是 False

先说结论：not used[i - 1]是更常用的写法，它的含义是“前一个相同元素没有被使用过，那么当前元素也不应该被使用”。这个剪枝发生在同一层横向遍历的过程中，确保重复元素在同一个搜索层级上只被使用一次。

另外一种写法used[i - 1] == True也能去重，但语义和剪枝的位置不同：它是让“重复元素按顺序->先后被使用”，等价于只保留原数组相对顺序下的一种排列方式。

两种写法时间和空间复杂度一致。我个人的习惯是记住not used[i - 1]，因为它在语义上更符合“同一层不允许重复起点”的直觉，且配合排序逻辑更好解释。

4.4 交换法如何去重

如果用交换法实现全排列 II，去重稍微麻烦一点，不能只靠排序。常见的方案是在 swap 之前检查：从start到i-1范围内，是否已经出现过nums[i]这个值。如果出现过，说明当前这个位置的同值元素已经换过一次了，再换就会产生重复排列。

void backtrack(vector<int>& nums, int start) { if (start == nums.size()) { result.push_back(nums); return; } for (int i = start; i < nums.size(); ++i) { bool duplicate = false; for (int j = start; j < i; ++j) { if (nums[j] == nums[i]) { duplicate = true; break; } } if (duplicate) continue; swap(nums[start], nums[i]); backtrack(nums, start + 1); swap(nums[start], nums[i]); } }

这个检查本质上是“局部去重”：在当前位置start，如果某个值已经和start交换过，那么后续再遇到相同值就不需要再换一次。它的思路和used数组剪枝异曲同工，但时间复杂度上多了一层内循环，总体更慢。

5. 复杂度分析为什么是 O(n × n!)

5.1 时间复杂度的推理过程

很多人背下了“全排列时间复杂度是 O(n × n!)”这个结论，但不知道它是怎么来的。这里给出一个直观的推理方式。

在回溯枚举的过程中，每一棵搜索树的叶子结点有 n 个元素，是一个完整排列；叶子结点的数量是 n!。但我们不能只看叶子结点，因为生成每个排列的过程中，还经历了路径拼接的操作，比如track.append(nums[i])、track.pop()、记录结果时的数组拷贝track[:]等，都是 O(n) 级别的操作。

所以总时间 = 叶子结点数量 × 每个叶子结点的记录成本 = n × n!。这是一个上界估计，实际运行时间会略小于这个值，因为中间结点也有成本，但整体量级就是这个。

5.2 空间复杂度的细节

递归过程中，递归栈的最大深度是 n，所以栈空间是 O(n)。加上used数组 O(n)、track存储 O(n)，算法本身的辅助空间是 O(n)。

如果你把结果集res也计算在内，那总空间就是 O(n × n!)，因为你要存下 n! 个排列，每个排列 n 个元素。这是题目要求“返回所有排列”的必然代价，不算额外浪费。

这里想提醒一点：在真正的工程项目里，n = 10 时输出 3628800 个排列已经会让内存飙升，n = 12 时是 4.79 亿个排列，基本不现实。所以全排列的暴力枚举只适合 n 比较小的情况，通常 n 不超过 10 或者 12。

5.3 为什么 n 稍大一点就“跑不动”

我们直观感受一下：

n = 8：40320 个排列；
n = 10：3628800 个排列，大约 360 万；
n = 11：39916800，接近 4000 万；
n = 12：479001600，接近 4.8 亿；
n = 15：1307674368000，万亿级别。

这个增长速度是阶乘级的，比指数级还可怕。所以全排列枚举只适用于小规模场景；一旦规模变大，必须想别的办法，比如剪枝、启发式搜索、动态规划（状态压缩）等。

这也是为什么很多优化算法的核心目标就是“避免枚举所有排列”。比如旅行商问题的状态压缩 DP，本质是牺牲空间换时间，把 n! 的复杂度压缩到 O(2^n × n)，虽然仍然很大，但比 n! 好太多了。

6. 迭代生成全排列：字典序与 next_permutation 原理

6.1 字典序是什么

字典序就是按照“字母表顺序”来排列所有结果，小的在前，大的在后。对于排列 1、2、3，字典序就是：

1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1

如果想要按照字典序输出全排列，可以依靠“找下一个字典序更大的排列”这个思路，反复执行直到找不到下一个为止。这个算法被称为next_permutation，C++ STL 的<algorithm>头文件里直接提供了现成实现。

6.2 手动实现 next_permutation 的四步法

以序列[1, 3, 2, 4]找下一个排列为例：

从右向左找第一个顺序对：从左往右看，找到第一个nums[i] < nums[i+1]的地方，记录位置 i；如果找不到，说明当前序列是降序的，已经是最大的排列；
从右向左找第一个大于 nums[i] 的数：记为位置 j；
交换 nums[i] 和 nums[j]；
把 i+1 到结尾的部分反转。

代码实现如下：

bool nextPermutation(vector<int>& nums) { int i = nums.size() - 2; while (i >= 0 && nums[i] >= nums[i + 1]) { i--; } if (i < 0) { reverse(nums.begin(), nums.end()); return false; } int j = nums.size() - 1; while (nums[j] <= nums[i]) { j--; } swap(nums[i], nums[j]); reverse(nums.begin() + i + 1, nums.end()); return true; }

用这个函数就能按字典序生成全部排列：

vector<vector<int>> permute(vector<int>& nums) { sort(nums.begin(), nums.end()); vector<vector<int>> res; do { res.push_back(nums); } while (nextPermutation(nums)); return res; }

这段代码非常经典，让“生成下一个排列”的复杂度变成 O(n)，生成所有排列的总复杂度依然是 O(n × n!)。

6.3 递归法输出的顺序是什么

用“选数法 + used 数组”的代码跑一遍[1, 2, 3]，输出顺序是：

1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1

刚好也是字典序。但如果你用前文说的“交换法”，输出顺序很可能就是：

1 2 3 1 3 2 2 1 3 2 3 1 3 2 1 3 1 2

最后两个的顺序不一样了。所以交换法生成的顺序不是严格字典序。这提醒我们：如果你的需求是字典序，用选数法更保险；如果你只关心“输出所有结果”，交换法更简洁高效。

7. 常见问题与调试实录

7.1 结果全是同一个值：引用拷贝的坑

这是我带新人时见过最多的问题。在 Java 里写res.add(path)，在 Python 里写res.append(track)，最后发现res里面全是同一个排列、而且长度是 n 的数组重复出现。原因很简单：你存入的是同一个对象的引用，递归回溯过程中这个对象一直被修改，最后所有引用都指向同一个最终状态。

正确的做法永远是拷贝一份当前路径的快照：

Java：new ArrayList<>(path)
Python：track[:]
C++：直接 pushnums，因为交换法里nums就是当前排列

7.2 忘记撤销导致的分支污染

如果你发现输出结果中出现了一些“渗透”的现象，比如第二个分支的路径里带着第一个分支的元素，十有八九是撤销步骤缺失。回溯算法的每一步“做选择”都必须有对应的“撤销选择”，两者必须成对出现。这就像进门前把钥匙放在鞋柜上，出门时必须再拿起来，不然下一趟进门的你就没钥匙了。

7.3 去重剪枝时忘记排序

全排列 II 的去重依赖排序，如果忘了sort，剪枝条件nums[i] == nums[i - 1]就找不到相邻重复元素，去重彻底失效。这个错误比较隐蔽，因为当测试用例是[1, 1, 2]时，数组已经是排序好的，你能过；换一组乱序用例[2, 1, 1]就翻车。所以写去重代码的第一步就是sort，没有例外。

7.4 交换法和状态数组混用的混淆

有些人写交换法去重时，从网上抄了used数组版本的剪枝条件，结果根本不生效。两种方法的搜索过程和状态管理方式完全不同，混用必然逻辑混乱。我的建议是：初学阶段老老实实只用一种框架。等你把“选数法”彻底练熟，再尝试“交换法”，不要在同一题里既用used又用swap。

7.5 基础问题速查表

问题现象	可能原因	解决方案
结果集全是同一个排列	引用拷贝而非值拷贝	压入结果时新建对象拷贝路径
结果数量正确但部分重复	未处理重复元素	排序 + 剪枝 / 交换法局部去重
结果顺序不是字典序	使用了交换法	改用选数法或改写为 next_permutation
递归深度报错 / 栈溢出	n 太大或终止条件缺失	检查 base case，或改用迭代法
剪枝条件不生效	忘记排序 / 判断条件写错	先 sort，再确认 used 状态
某些分支缺失	递归返回值或循环范围写错	检查 for 循环的起始和终止边界

8. 实操体会与面试经验

8.1 一道题背后的算法思想网络

全排列表面上是一道题，实际上是好几个重要思想的集合体：

DFS 框架：深搜一棵隐式状态树；
回溯 + 状态重置：递归后恢复现场；
剪枝优化：去重、排除无效分支；
递归转迭代：手动管理栈 / 使用 next_permutation；
复杂度量级感：阶乘暴力的边界在哪里。

如果你能在一个晚上把全排列从普通版写到去重版，再手动实现一次next_permutation，那么你对回溯算法的理解会扎实很多。之后再去碰组合总和、子集、N 皇后、括号生成这类问题，你会发现它们的框架几乎一模一样，差别只在选择列表的定义和终止条件的写法。

8.2 面试中被追问过的问题

面试官常常在看完全排列代码后追问这几个问题，我整理一下，方便你提前准备：

一是“这个算法的复杂度是多少”。答案要分清楚时间复杂度和空间复杂度，并且解释为什么是 O(n × n!)。

二是“如果有重复元素怎么处理”。要能说出排序 + 剪枝的思路，并且写清楚used[i - 1]的条件和含义。

三是“为什么撤销选择”。这是考察对回溯本质的理解，不只是背模板。

四是“能不能不用递归实现”。如果能现场写出next_permutation的迭代版本，会是非常加分的亮点。

五是“数据规模很大怎么办”。这里可以聊剪枝、启发式搜索、状态压缩动态规划等优化思路，展示你的算法视野。

8.3 再分享一个小技巧

如果你在做题时怕写错回溯代码，可以先用一组小数据（比如[1, 2, 3]）把整棵递归树手动画一遍，标清楚每一层进入时的路径、选择列表，然后照着这棵树去核对代码的每一步行为。这个方法很笨，但对建立回溯的直觉特别有效，我教过不少人从“背模板”变成“真正理解回溯”。

另外我建议你学全排列的时候，顺手实现一下“下一个排列”和“第 k 个排列”这两个变体题。它们一个考察迭代思维，一个考察数学计算与康托展开，能把全排列相关的知识网补得相当完整。特别是“第 k 个排列”这道题，很多人第一次见完全懵，但如果你理解排列的阶乘系统，就会发现它其实就是一个“按位确定”的过程。

最后说一句：全排列算法的暴力性质决定了它不能解决超大规模问题，但把它当成理解递归、回溯、剪枝的切入点，它带来的收益远远超过它本身的应用范围。我自己在写了很多年工程代码之后回头看，最怀念的依然是当年在纸上画递归树、一步步模拟回溯流程的那个下午。有些基础功，真的怎么强调都不过分。