提到经典算法很多人第一反应是排序、二分、动态规划但真正在笔试现场“卡壳最狠”的往往是全排列。全排列问题看起来简单一句话就能说清楚“给定n个元素输出所有可能的排列顺序”可真到要手写代码的时候递归、回溯、剪枝、去重、字典序、复杂度这些概念一拥而上不少人就开始迷糊了。这篇文我想把全排列这个经典算法彻底拆开——从最朴素的回溯模板到重复元素去重这样的高频变体再到不依赖递归的字典序实现顺带聊聊复杂度量级和实际项目里的应用。不管你是准备面试笔试、刷算法题还是工作中突然要暴力枚举一组顺序这篇应该都能给你一套能直接抄走的东西。1. 先搞清楚全排列到底在求什么1.1 问题定义与数学背景全排列用数学语言说很简单对于集合 {1, 2, 3, ..., n}输出它的所有排列满足每个排列包含全部n个元素且不重复。数量是n!也就是n的阶乘3个元素有6种排列4个元素有24种5个元素有120种。这个阶乘增长非常夸张后面我会专门算一笔账让你对“什么规模能暴力枚举、什么规模想都别想”有个直观认知。很多人在初学阶段容易把全排列和“可重复组合”混在一起。比如问“用数字1到3能组成多少个三位数”答案是27个因为允许重复。而全排列不允许重复使用同一个元素所以只有6个。这两者的区别正是算法里“是否使用used数组”的根源全排列每个位置上的元素不能重复出现。另一个容易忽略的点是全排列的输出顺序在不同算法里可能不一样。比如回溯法按used数组顺序扫描输出可能是1-2-3、1-3-2、2-1-3……而交换法输出的顺序完全不同。很多题目要求按字典序输出这个细节会在第4章详细讲。1.2 我为什么说它是“算法地基”全排列不只是个单独的知识点它其实是很多搜索类问题的地基。比如八皇后问题可以转化为“每行放一个皇后皇后所在的列号构成一个排列再检查对角线是否冲突”任务调度暴力枚举执行顺序时本质上是在枚举所有排列甚至一些“下一个排列”“第K个排列”的题目核心也是全排列生成算法的变形。我在实际工作中遇到过这样的场景一个接口有4个可选参数需要测试不同参数顺序对结果是否有影响简单粗暴的办法就是把参数顺序的所有排列跑一遍。虽然听起来很土但却是最可靠的验证方式。这种时候一个清晰的全排列模板比什么都管用。1.3 学习全排列的几个常见误区第一以为全排列的规模是n^n匆匆写个三层循环结果元素可能被重复使用输出反而变成了“有放回排列”。第二觉得输出顺序无所谓结果题目要求字典序时手忙脚乱。第三也是最多人栽跟头的——以为全排列只能靠递归非要手撕递归搞得自己晕头转向。实际上全排列有至少三条路used数组回溯、交换递归、字典序迭代每条路适合的场景都不一样后面依次展开。2. 回溯法写出全排列的第一把钥匙2.1 回溯算法的核心思想三个坑位的故事用生活化的方式理解全排列假设你有3个不同颜色的球面前有3个坑位你要把球依次放进坑里每个坑放一个球问一共有多少种放法。第一个坑有3种选择第二个坑只能从剩下的2个球里选第三个坑只剩1个球。回溯法做的事情就是模拟这个过程选一个球放进坑里记住这个球被用过了然后去处理下一个坑如果所有坑都填满了输出当前结果如果某个坑没有球可选了就“回头”——把上一个坑里的球拿回来换一个球重新试。这个拿回来的动作就是“回溯”。算法里对应两份关键数据结构path数组记录当前填坑的顺序used数组标记某个元素是否已经被放进当前路径。递归深度就是当前填到第几个坑位。2.2 C语言手写最稳的回溯模板直接给一个我实际用过很多次的C语言模板思路清晰几乎不会写错#include stdio.h int n; int nums[100]; // 原始数组 int used[100]; // 标记某个下标是否已经被使用 int path[100]; // 当前路径 void dfs(int depth) { // 递归出口所有坑位都填满了 if (depth n) { for (int i 0; i n; i) { printf(%d , path[i]); } printf(\n); return; } // 遍历所有元素尝试填入当前坑位 for (int i 0; i n; i) { if (used[i]) continue; // 已经用过的元素不能再用 used[i] 1; // 标记已用 path[depth] nums[i]; // 填入坑位 dfs(depth 1); // 递归填下一个坑 used[i] 0; // 撤销标记恢复现场 } } int main() { n 3; nums[0] 1; nums[1] 2; nums[2] 3; dfs(0); return 0; }这段代码最有价值的习惯是用下标标记used而不是用数值标记used。如果数组里有重复数字时用数值标记会直接把重复数字当成同一个元素导致大量排列被漏掉。用下标标记即使两个位置的值相同它们在逻辑上也是不同元素这样后续做去重才有操作空间。我在初学阶段踩过一个典型坑递归返回之后忘了恢复used状态。结果就是第一层选了1之后后面所有层都认为1已经被用过只输出了1-2-3一个排列就结束了。恢复现场这件事是回溯算法的灵魂。2.3 交换法代码更短但更容易绕晕另一条很常见的路线是交换法。它的思路不是“选数填坑”而是“当前位置和后面某个元素交换”void permute(int arr[], int start, int n) { if (start n) { for (int i 0; i n; i) printf(%d , arr[i]); printf(\n); return; } for (int i start; i n; i) { swap(arr[start], arr[i]); // 把第i个元素放到当前start位置 permute(arr, start 1, n); swap(arr[start], arr[i]); // 交换回去恢复现场 } }这个写法不需要used数组代码短了不少看起来更“聪明”。但它有个隐蔽问题一旦原数组里有重复元素直接跑会输出相同的排列多次。虽然可以在每一层加一个Set集合来去重但处理起来反而比used数组模板更繁琐。我的建议是面试或者笔试时优先用used数组模板因为它天然支持去重扩展不容易翻车。交换法适合你已经很清楚自己在做什么或者题目本身需要原地产出排列结果、不关心后续去重的时候。两个模板都要会但脑子里要清楚哪个是主手、哪个是备胎。2.4 输出顺序的细节细心的读者会发现如果nums数组是升序排列used数组从小到大扫描回溯法输出的排列就是字典序。因为每一层都是按升序尝试第一个未使用的元素。但如果nums乱序输出顺序就跟着乱。LeetCode上很多全排列题目不要求输出顺序但竞赛题的“字典序输出”要求本质上只需要你先排个序再跑回溯。3. 高频变体重复元素的去重问题全排列 II 专属坑3.1 为什么重复元素会带来重复排列LeetCode 47题“全排列 II”是面试中出现频率非常高的变体给定一个可包含重复数字的序列返回所有不重复的全排列。比如输入{1, 1, 2}朴素回溯会输出6个排列但其中{1a, 1b, 2}和{1b, 1a, 2}在数值上都是1-1-2只能算一个。最终答案只有3个1-1-2、1-2-1、2-1-1。核心问题在于两个值相同的元素在“填坑”时被当成了不同个体它们之间互换位置产生的排列在数值上没有区别。要解决这个问题思路只有一个——在搜索过程中把“对称的重复分支”剪掉。3.2 去重方案一每层一个Set直观但有开销最直观的做法是在每一层递归中建立一个Set记录当前坑位已经尝试过哪些数值。如果发现当前数值在本层已经试过就直接跳过SetInteger seen new HashSet(); for (int i 0; i nums.length; i) { if (used[i]) continue; if (seen.contains(nums[i])) continue; // 本层已经用过这个值 seen.add(nums[i]); used[i] true; path.add(nums[i]); dfs(...); used[i] false; path.remove(path.size() - 1); }这种写法思路很直接代码也不难但每一层都要维护一个Set空间开销是O(n)。而且对于值域很大的场景Set的哈希计算本身也有一点性能损耗。好在全排列的数据规模通常不大这种方案作为“保底方案”完全是合格的。3.3 去重方案二先排序再加剪枝最推荐的做法力扣官方推荐的方案是“先排序然后在循环里加一个剪枝条件”。我直接给出Java版本的完整实现这个模板我刷题用了很多次class Solution { public ListListInteger permuteUnique(int[] nums) { ListListInteger res new ArrayList(); Arrays.sort(nums); // 排序是剪枝的前提 boolean[] used new boolean[nums.length]; backtrack(nums, used, new ArrayList(), res); return res; } private void backtrack(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; // 核心剪枝相同值且前一个没有被使用说明是同一层的重复选择 if (i 0 nums[i] nums[i - 1] !used[i - 1]) continue; used[i] true; path.add(nums[i]); backtrack(nums, used, path, res); used[i] false; path.remove(path.size() - 1); } } }很多人第一次看到这段代码都会问为什么剪枝条件是!used[i-1]而不是used[i-1]把这个想透了全排列去重就真正掌握了。我用{1a, 1b, 2}举个例子1a和1b是数值相同的两个元素排序后1a在1b前面。当第一层尝试选1b作为第一个元素时因为1a还没有被选入当前路径used[0]为false所以条件nums[1] nums[0] !used[0]为true直接跳过1b开头这一整个分支。这是正确的因为以1开头这个前缀在1a的分支里已经完整枚举过了再走一遍1b开头就是重复劳动。至于used[i-1]这个写法它的语义变成了“前一个相同值的元素已经被当前路径使用”会剪掉很多本不该剪的分支最终输出的排列要么漏解要么依然有重复。我在一次代码评审时就见过同事这么写结果用例输出5个排列里面还有两个重复的排查了半天。所以看到这个条件一定要确认自己写的是!used[i-1]。3.4 去重场景的隐藏误区输入数组必须有序排序是这个剪枝方案的前提。如果不排序数组里相同值分散在不同位置nums[i] nums[i - 1]这个比较就失去了意义。很多人在写全排列II时明明已经写对了剪枝逻辑但忘记在最前面排序结果输出依然有重复。这个坑特别隐蔽因为小数据量时可能碰巧看不出问题但一旦数组长度变大重复排列会成倍出现。另一个容易被忽视的细节是用于去重的“相同值比较”只和前一个位置比较所以排序后相同的值一定相邻这个相邻关系保证了我们只需看前一个元素就能完整覆盖“所有值相同的重复分支”。4. 字典序法换一条不依赖递归的生成路径4.1 什么是字典序全排列如果你把“abc”按字母表顺序排列所有排列得到的就是字典序abc、acb、bac、bca、cab、cba。换成数字就是1-2-3、1-3-2、2-1-3、2-3-1、3-1-2、3-2-1。字典序全排列有一个特点每输出一个排列下一个一定是在数值顺序上“刚好比当前排列大一点”的那个。也就是说它像计数器一样从最小排列一路递增到最大排列。这个“找下一个更大排列”的思路恰好是LeetCode 31题“下一个排列”的标准解法也是C标准库函数next_permutation的实现原理。4.2 手写 next_permutation四步搞定不依赖任何语言库手写一个求下一个字典序排列的算法只需要四步从右向左找到第一个“相邻升序对”也就是满足a[i] a[i1]的最靠右的i。再从右向左找到第一个大于a[i]的元素位置j。交换a[i]和a[j]。将a[i1]到数组末尾整体反转。用{1, 2, 3}做一遍手动推演找第一个相邻升序对从右向左看3和2不是升序2和1是升序所以i1对应元素2从右向左找第一个大于2的元素是3位置j2交换2和3得到{1, 3, 2}反转位置2到末尾也就是第二个元素之后的全部位置2是最后一个元素反转后还是{1, 3, 2}。所以{1, 2, 3}的下一个排列是{1, 3, 2}完全符合字典序。C语言实现如下int nextPermutation(int* a, int n) { // 1. 从右向左找第一个升序对 int i n - 2; while (i 0 a[i] a[i 1]) { i--; } // 已经是从大到小的最大排列没有下一个 if (i 0) { return 0; } // 2. 从右向左找第一个大于a[i]的元素 int j n - 1; while (a[j] a[i]) { j--; } // 3. 交换 int tmp a[i]; a[i] a[j]; a[j] tmp; // 4. 反转a[i1]到末尾 int left i 1; int right n - 1; while (left right) { int t a[left]; a[left] a[right]; a[right] t; left; right--; } return 1; }有了这个函数生成所有全排列就非常简单了先排序得到最小字典序排列然后不断调用nextPermutation直到它返回0sort(a, a n); do { // 输出当前排列 } while (nextPermutation(a, n));注意这里用的是do-while而不是while因为当前排列本身必须被处理。这个细节我见过不少初学者忽略结果第一个排列永远不输出。4.3 为什么字典序法适合“求下一个”场景回溯法的优势是“从零生成所有排列”但如果你只需要“给定某个排列求字典序的下一个”回溯法就非常笨拙——你必须把之前的排列全部生成一遍才能找到目标。而字典序法的好处恰恰在于“增量生成”给定任意排列它都能在O(n)时间内直接算出下一个排列。我举一个具体场景你在做一个优惠券抽奖系统要按顺序发放一批礼品组合每个组合是一个排列而且必须按字典序顺序发放以便做日志检索。这种场景下字典序法天然适合因为不需要每次都从头枚举。4.4 三种实现方式的选型对比维度used数组回溯交换递归字典序迭代输出顺序取决于原始数组顺序排序后可为字典序非字典序稳定字典序去重方案排序 !used[i-1]剪枝需要额外的Set天然跳过重复值空间复杂度O(n)O(n)调用栈O(1)实现难度中等思路清晰代码短但易出错需要记忆四步流程典型场景面试笔试首选原地输出、短代码求下一个排列、字典序输出我在实际刷题时全排列生成一般用used数组回溯特殊需要“下一个排列”时切到字典序法。两种方法互补没必要非得出个孰优孰劣。5. 复杂度分析与性能实测n到底能开到多大5.1 理论复杂度推导全排列生成的下界非常明确排列总数是n!每个排列至少要输出n个元素所以任何“生成并输出所有排列”的算法时间复杂度至少是O(n·n!)。这个下界没法优化因为我们要求的就是全部排列。回溯法每递归一层要扫描一次used数组找可用元素整体复杂度同样是O(n·n!)但常数项偏大因为每个节点都要做for循环遍历。字典序法每个排列只需做一次线性扫描和一次反转常数小在不输出、只生成的情况下通常比回溯更快。空间上回溯法额外用了path数组和used数组加上递归调用栈总体是O(n)。字典序法除了原始数组外几乎不需要额外空间是O(1)。这个差异在极致性能场景下值得考虑但对日常刷题影响不大。5.2 一张表看清规模量级nn!说明5120随便枚举840320暴力枚举毫无压力103628800生成没问题全输出已需要谨慎12约4.79亿已经不现实需要考虑剪枝或换算法15约1.3万亿就算每秒生成1亿个也需要13万秒这张表给我最大的提醒是全排列的暴力枚举只能用于n≤10左右的规模。一旦n超过12不管算法本身多优化排列数量本身的爆炸性增长都会压垮一切。所以做题时如果发现n≥12还要求枚举所有排列第一反应应该是有特殊剪枝条件或者需要数学方法而不是硬着头皮写全排列。5.3 我的实测数据不严谨但可供参考我在自己机器上i7-9700K16GB内存Win10 gcc O2编译跑过一次测试只生成排列不打印避免IO干扰结果C语言used回溯生成n10的全部排列大约0.15秒左右。字典序法生成同样规模大约0.08秒左右。n11时回溯法大约1.5秒n12直接到了18秒以上。这个对比能明显看出字典序法的常数优势。但注意一旦开启打印到控制台IO就成了绝对瓶颈n8的40320个排列刷屏已经让控制台卡得难受。如果你需要在程序中输出大量排列到文件建议使用批量缓冲写入逐条打印谁试谁知道。5.4 性能优化思路优化的第一方向永远是剪枝。全排列本身很难剪但全排列问题的变体往往带有约束条件比如八皇后中对角线冲突检查、数独中的行列约束。每剪掉一层节省的是一个子树的所有排列收益是指数级的。第二方向是减少复制和IO开销。回溯模板里路径数组可以预先分配好不要在递归里反复new。输出时用缓冲区拼接字符串批量write而不是每条排列都调用println。第三方向是并行。全排列天然可以分块固定前k个元素把剩余元素的全排列分给不同线程。不过这个方案的收益会被输出IO和线程调度开销抵消性价比不高仅作了解。6. 全排列的延伸应用与一套可复制的解题模板6.1 从全排列到N皇后一个最经典的变体N皇后问题要求在一个N×N棋盘上放置N个皇后使它们彼此不能攻击。换个角度看每一行只能放一个皇后所以皇后所在列号天然构成一个N个元素的排列。因此所有合法皇后布局一定藏在全排列里再去掉对角线冲突的就是答案。回溯模板稍做修改就能解决填第depth行时除了检查该列是否被使用过还要检查当前列号和之前已放皇后的列号的差是否等于行号的差。如果不相等就继续递归相等则放弃。这个变体是检验你是否真正理解“选、判、递归、撤销”四步流程的试金石。6.2 一套通用模板全排列问法三步走无论题目是简单全排列、全排列II还是一堆花里胡哨的变体我建议你固定一套打法看有无重复有重复先排序排序的目的是让相同值相邻是剪枝的前提。确定递归参数used数组 当前深度或者path是标配有额外约束再加参数。循环里做四步检查是否可用、标记已用、加入path或填入数组、递归、撤销标记、移除path。下面给一个C通用模板我刷题时直接复制改一改就能用#include vector #include algorithm using namespace std; void backtrack(vectorint nums, vectorbool used, vectorint path, vectorvectorint res) { if (path.size() nums.size()) { res.push_back(path); return; } for (int i 0; i nums.size(); i) { if (used[i]) continue; if (i 0 nums[i] nums[i - 1] !used[i - 1]) continue; used[i] true; path.push_back(nums[i]); backtrack(nums, used, path, res); used[i] false; path.pop_back(); } }这个模板同时处理了无重复和有重复两种场景如果数组本身就无重复那个剪枝条件永远不会触发如果有重复排序后剪枝自动生效。一个模板走天下不用记多个版本。6.3 回溯法通用框架的“记忆口诀”我在指导初学者的时候经常让他们记住八个字“选、判、递归、撤销”。选就是从剩余元素中挑一个判就是检查这个选择是否满足所有约束递归就是带着新状态进入下一层撤销就是把状态恢复原样尝试下一个选项。四个动作缺一不可顺序不能乱。具体的代码排布上需要注意三点撤销动作必须放在循环体内、递归调用之后而不是放在循环外。放在循环外会导致一次回溯就把整个路径清空。递归出口的判断要放在进入for循环之前否则会在path满之后继续往下走。加入path和标记used的顺序没有严格要求但保持“先标记再加入、先移除再解除标记”的一致习惯能减少心智负担。6.4 什么时候能暴力枚举什么时候必须换思路这是我在实际项目中体会最深的一点。全排列之所以让人欲罢不能是因为它能保证找到所有解但在数据规模稍大时就会变成性能灾难。一个实用的判断标准n ≤ 8放心暴力。9 ≤ n ≤ 10可以做但谨慎评估耗时尤其要控制输出量。n ≥ 12想都不要想无脑全排列要么加约束剪枝要么换贪心/动态规划/状态压缩DP。状态压缩DP和全排列在语义上其实有深刻联系很多“从n个物品中选出一个排列来最优化目标”的问题本质上等于全排列枚举但通过DP把阶乘复杂度降到O(n·2^n)。这就是为什么学好全排列不只是为了刷题它能帮你建立对“枚举所有排列到底有多贵”的直觉从而在真正设计算法时做出正确的取舍。6.5 面试现场的一些个人经验最后分享一点面试经验全排列是面试官非常喜欢考的手写题因为它能快速检验算法基础。我见过很多候选人对这题“看过、懂思路”但真拿到白板就开始乱。原因往往是没有一个固定的模板肌肉记忆。我个人的建议是把第6.2节那套模板练到闭着眼睛都能写出来并且能在两分钟内默写完。同时准备一个简短清晰的“解释框架”先说这是典型的回溯问题再讲递归的终止条件然后讲如何用used数组避免重复使用元素最后提一句如果有重复元素加排序剪枝。这个框架讲完面试官基本就能确定你确实理解了这道题而不只是背了代码。如果面试官继续追问“还能怎么优化”就把第4章的字典序法丢出来顺带讲清楚两者在输出顺序和空间复杂度上的差异。能走到这一步这道题的分数基本就拿到手了。