全排列是个很奇妙的东西。它可能是很多人接触“回溯算法”的第一道门也是面试里出镜率极高的常客——从最简单的“三个数字有几种排法”到力扣上那个经典的“全排列 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! 6n 4就是 4! 24n 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: vectorvectorint result; void backtrack(vectorint 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]); // 撤销交换 } } vectorvectorint permute(vectorint nums) { backtrack(nums, 0); return result; } };这段代码每次递归到最底层时nums本身就是一个合法的排列所以直接把nums压入结果。这里最需要注意的还是那两行swap换完之后必须再换回来否则下一次循环的起点就被污染了。交换法的代码更简洁不需要used数组但它的排列生成顺序不是字典序后面会细说。如果你只求列出所有排列不要求顺序交换法更清爽如果要求按字典序输出用“选数法 used 数组”更自然。3.3 Java 版本实现兼顾代码规范与工具类class Solution { ListListInteger res new ArrayList(); boolean[] used; int n; public ListListInteger permute(int[] nums) { n nums.length; used new boolean[n]; DequeInteger path new ArrayDeque(); dfs(nums, path); return res; } private void dfs(int[] nums, DequeInteger 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(vectorint 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 840320 个排列n 103628800 个排列大约 360 万n 1139916800接近 4000 万n 12479001600接近 4.8 亿n 151307674368000万亿级别。这个增长速度是阶乘级的比指数级还可怕。所以全排列枚举只适用于小规模场景一旦规模变大必须想别的办法比如剪枝、启发式搜索、动态规划状态压缩等。这也是为什么很多优化算法的核心目标就是“避免枚举所有排列”。比如旅行商问题的状态压缩 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_permutationC STL 的algorithm头文件里直接提供了现成实现。6.2 手动实现 next_permutation 的四步法以序列[1, 3, 2, 4]找下一个排列为例从右向左找第一个顺序对从左往右看找到第一个nums[i] nums[i1]的地方记录位置 i如果找不到说明当前序列是降序的已经是最大的排列从右向左找第一个大于 nums[i] 的数记为位置 j交换 nums[i] 和 nums[j]把 i1 到结尾的部分反转。代码实现如下bool nextPermutation(vectorint 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; }用这个函数就能按字典序生成全部排列vectorvectorint permute(vectorint nums) { sort(nums.begin(), nums.end()); vectorvectorint 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 的数组重复出现。原因很简单你存入的是同一个对象的引用递归回溯过程中这个对象一直被修改最后所有引用都指向同一个最终状态。正确的做法永远是拷贝一份当前路径的快照Javanew ArrayList(path)Pythontrack[:]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 个排列”这道题很多人第一次见完全懵但如果你理解排列的阶乘系统就会发现它其实就是一个“按位确定”的过程。最后说一句全排列算法的暴力性质决定了它不能解决超大规模问题但把它当成理解递归、回溯、剪枝的切入点它带来的收益远远超过它本身的应用范围。我自己在写了很多年工程代码之后回头看最怀念的依然是当年在纸上画递归树、一步步模拟回溯流程的那个下午。有些基础功真的怎么强调都不过分。