全排列问题说穿了就是把一组元素按不同顺序全部摆一遍一个不重、一个不漏。它看着简单——三个数只有6种排法四个数24种——但真正动手写的时候很多人第一次都会卡在两件事上怎么把已经选过的数排除掉以及递归回来之后状态怎么还原。这道题在算法入门里的地位有点像学乐器时的音阶练习本身不难却是回溯思想的样板间把它啃透了子集、组合、N皇后、解数独都是换个壳子的事。我打算把全排列从头到尾拆一遍最朴素的标记数组写法、省空间的交换写法、带重复元素的去重版本、字典序版本还有第k个排列那道经典的数学解法最后聊聊我在刷题和面试里踩过的坑。不管你是刚接触递归的新手还是想回头重新梳理一遍回溯模板的老手这篇应该都能捞到点实用的东西。1. 全排列到底在解决什么问题1.1 从一个座位安排的小场景说起假设宿舍六个人要排一列拍照摄影师让你给出所有可能的站位。你会怎么想第一个人有6种选法第二个还剩5种第三个剩4种……一路乘下去就是 6×5×4×3×2×1 720 种。这就是全排列最原始的定义从 n 个不同的元素里按顺序取出 n 个所有可能的取法总数是 n 的阶乘。生活中的例子其实不少。比如打牌时估算某种起手的可能性、给球员排罚球顺序、给任务排执行次序找最优解底层都是排列枚举。区别只在于有的场景你只需要计数数学公式一算就完事有的场景你必须把每一种具体的顺序都列出来再逐个评估这时候就只能老老实实搜索。算法题里的全排列绝大多数属于后者。题目会给你一个不含重复数字的数组要求返回它所有可能的全排列顺序不限。输入是[1,2,3]输出就是[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]这六组。看着平平无奇但它考察的东西一点都不少递归的边界、状态的标记与还原、路径的记录与快照一个环节写错就全盘皆输。1.2 阶乘的膨胀速度为什么 n 一大就废了很多人对阶乘没有直观感受觉得 n10 能有多大事。我列个表你就明白了nn! 的值直观感受5120一秒跑完毫无压力840320还能接受103628800三百六十万内存开始吃紧12479001600四亿七千万基本告别暴力151307674368000一万三千亿洗洗睡吧这张表想说的是全排列算法的时间复杂度天然带着 n! 这个因子任何基于枚举的解法都逃不掉。所以面试里给出的 n 通常不会超过 8 到 10出题人不是心慈手软而是再大就没法在合理时间内验证结果了。理解这一点很重要——当你发现一道题的最优解仍然是阶乘级别时说明题目本身就不指望你优化掉这个下界你要做的是把常数项和空间开销压下去而不是妄图找出多项式解法。这也顺带解释了一个常见疑惑为什么全排列题很少有大数据量的测试用例。不是测试数据偷懒是数学不允许。1.3 全排列的三种常见问法刷题刷多了会发现全排列这个知识点衍生出的题目大致分三类每类的解法重心完全不同第一类是输出全部排列这是最基础的形态考的纯粹是回溯框架搭得对不对。第二类是判断下一个排列也就是next_permutation那套逻辑考的是对字典序的理解和原地修改的能力它有个很妙的 O(n) 解法跟回溯没半点关系。第三类是带重复元素的排列比如数组是[1,1,2]正确答案只有[[1,1,2],[1,2,1],[2,1,1]]三组多一个都算错考的是你对同一层不能选重复值这个剪枝条件的理解深度。还有一类变体是求第k个排列看起来像是要老老实实生成再取第k个其实用数学方法可以一步到位直接构造是道很能体现思维差距的题。这四种问法我在后面会逐个拆开讲先记住它们的共同点都在围着顺序和不重复这两件事打转。2. 核心思路回溯框架的三步走2.1 把问题看成一棵决策树理解全排列最快的方式是把它画成一棵树。以[1,2,3]为例根节点是空路径第一层有三个分支分别选 1、2、3。选了 1 之后进入第二层还能从剩下的 2、3 里挑于是又分出两个分支。再往下走一层只剩一个数字可选走到第三层结束路径长度凑满 3就是一个完整的排列。数一下叶子节点第一层3个分支每个分支下面2个每个再下面1个3×2×1 6正好对应 3! 个排列。这棵树有个学名叫做决策树或者状态空间树回溯算法的本质就是深度优先地遍历这棵树每走到一个叶子节点就收集一次答案。用树的视角看很多细节就自然清楚了。为什么需要撤销因为你从父节点走到子节点之后还要回到父节点去尝试另一条分支不把状态恢复原样第二条分支就是在错误的基础上继续走的。为什么需要标记因为要记录哪些数字在这一条路径上已经被用掉了避免同一个数字在一组排列里出现两次。这两个问题一旦想通代码基本就是照着树的结构翻译。提示如果递归写得晕别盯着代码看拿张纸把[1,2,3]的决策树画出来手动模拟一遍深度优先的走法走完一遍代码自然就顺了。这是我最推荐的入门方式比看十篇解析都管用。2.2 选择、递归、撤销回溯的三板斧任何回溯代码剥掉外衣都剩下三个动作我习惯叫它三板斧做选择把当前元素加入路径同时把它的标记位设成已使用。进入下一层递归在当前选择的基础上继续往下走。撤销选择递归返回后把刚才加进去的元素弹出把标记位还原。这三步的顺序是死规矩不能乱。特别是第三步新手最容易忘。忘了会怎样假设你在处理[1,2,3]第一层选了1第二层选了2第三层选了3得到[1,2,3]这一步没问题。然后回溯到第二层准备把2换成3如果你没有把2的标记清掉程序会认为2还被占用着第二层就只能选3第三层又只剩2结果[1,3,2]算是勉强对了。但再往上一层回溯时因为1的标记也没清第一层永远只能选1最终你只会得到两组答案另外四组凭空消失。这种 Bug 的阴险之处在于它不报错不崩溃只是答案变少了。你如果只拿[1,2,3]手动测一遍可能还以为自己写对了。所以写完回溯代码第一件事就是检查撤销逻辑是否和选择逻辑严格对称加了几行代码就得对应还回去几行。2.3 到什么程度算走到了头递归函数开头必须有个终止条件全排列里这个条件很直白路径长度等于数组长度说明所有元素都已经被安排好了位置直接把当前路径的一份拷贝存进结果集然后返回。这里有个细节必须强调存进结果集时一定要做深拷贝。Python 里要写path[:]或者list(path)Java 里要写new ArrayList(path)C 里path本身是值传递直接 push 就行。如果你偷懒把path这个引用直接塞进去等回溯把里面的元素一个个弹空你结果集里存的就全是一堆空列表了。这个坑我当年踩过调试了半小时才反应过来因为打印结果的时候看到的是六个空数组特别迷惑。另外判断条件的写法也有讲究。有人喜欢在进入函数时用if len(path) n判断有人喜欢在循环里判断if len(path) n - 1然后直接收集。两种写法都能跑但第一种更符合直觉也更不容易出错我建议统一用第一种。3. 标记数组法最直观的写法3.1 完整代码与逐行拆解标记数组法是教科书标准解法也是我最推荐新手先掌握的一版。核心就一个布尔数组记录某个下标上的元素有没有被用过。def permute(nums): 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 # 已使用跳过 used[i] True # 做选择 path.append(nums[i]) dfs() # 递归下一层 path.pop() # 撤销选择 used[i] False # 还原标记 dfs() return res逐行看下来used数组的作用是标记下标 i 上的数字已经被当前这条路径用了注意标记的是下标不是数值这一点在去重章节里会变得非常关键。path记录当前路径res收集所有完整排列。循环从 0 到 n-1每次都从数组头部开始扫遇到没用过的就选这种做法看起来有点粗暴但它保证了下标顺序和数值选择顺序完全解耦写起来最不容易出错。3.2 状态还原为什么不能忘上面代码里最后两行path.pop()和used[i] False就是撤销动作。我再强调一次它们为什么必须在同一个缩进层级里紧跟在dfs()后面。深度优先搜索的走法是一条路走到黑撞墙了退回来换条路。当你从第 i 个分支退回来的时候程序的状态必须回到选择第 i 个元素之前的样子否则下一个分支i1就是在污染过的环境下启动的。这就像你玩迷宫回溯走到死胡同时要退回到上一个岔路口而不是站在死胡同里原地思考。有一个验证自己写对没写对的小技巧在 dfs 函数末尾加一行断言检查进入函数时的状态和退出时是否一致。当然正式提交时要删掉但调试阶段非常有用。如果断言失败说明你的撤销逻辑漏了某一步。3.3 三语言对照与易错点同一套逻辑换到 Java 和 C 里结构完全一样区别只在数据结构的用法上class Solution { ListListInteger res new ArrayList(); ListInteger path new ArrayList(); boolean[] used; public ListListInteger permute(int[] nums) { used new boolean[nums.length]; dfs(nums); return res; } private void dfs(int[] nums) { 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); path.remove(path.size() - 1); // 移除最后一个 used[i] false; } } }class Solution { public: vectorvectorint res; vectorint path; vectorbool used; vectorvectorint permute(vectorint nums) { used.assign(nums.size(), false); dfs(nums); return res; } void dfs(vectorint nums) { if (path.size() nums.size()) { res.push_back(path); // vector 是值语义自动拷贝 return; } for (int i 0; i nums.size(); i) { if (used[i]) continue; used[i] true; path.push_back(nums[i]); dfs(nums); path.pop_back(); used[i] false; } } };三个语言版本里有几个容易翻车的点。Java 的path.remove(path.size() - 1)千万别写成path.remove(nums[i])因为ListInteger有个重载是remove(int index)和remove(Object o)传 int 进去走的是按下标删除传 Integer 对象走的是按值删除一旦数组里有重复值按值删除会删掉第一个匹配的路径就乱了。这是个极其经典的 Java 坑。C 相对来说最省心res.push_back(path)直接值拷贝不用操心深浅拷贝问题。4. 交换法省掉一个数组的原地版本4.1 思路与代码交换法的想法是与其用一个数组记录谁被用了不如把已经确定的元素挪到数组前面靠位置本身来划分已用和未用。具体做法是维护一个下标index表示前index个位置已经确定从index到末尾是待选区间。每一层循环里依次把index位置的元素和它后面的每个元素交换交换完递归下一层回来再换回去。def permute(nums): n len(nums) res [] def dfs(index): # index 走到了末尾说明所有位置都确定 if index n: res.append(nums[:]) return for i in range(index, n): nums[index], nums[i] nums[i], nums[index] # 把第 i 个换到 index dfs(index 1) # 递归剩余位置 nums[index], nums[i] nums[i], nums[index] # 换回来 dfs(0) return res这段代码短小精悍好处很明显不需要额外的used数组空间上省了 O(n)而且不用每次从 0 开始扫描整个数组循环只从index开始常数上也有优势。执行效率在实际跑分里通常比标记数组法快一些。4.2 两种写法的对比对比维度标记数组法交换法额外空间O(n) 的 used 数组O(1) 额外空间循环范围每次扫全数组 0 到 n-1只扫 index 到 n-1结果顺序天然保证字典序顺序被打乱支持去重容易加一个剪枝困难逻辑绕易理解程度高中等适用场景通用首推无重复元素且追求效率从表里能看出来交换法在无重复元素这个前提下确实更优但一旦题目要求去重它的复杂度就上来了。所以我个人的建议是面试时优先写标记数组法因为它的逻辑最通用去重、剪枝加进去都很自然面试官也能一眼看懂你的思路交换法适合在有性能要求、且元素互不相同的场景下使用。4.3 交换法的两个坑第一个坑是结果顺序被打乱。标记数组法从下标 0 开始逐层扫描得到的排列天然是按字典序排列的很多题会直接拿来用。交换法因为是把后面的元素换到前面得到的顺序很随机如果题目明确要求按字典序返回所有排列你就得多一步排序或者干脆换回标记数组法加排序的思路。第二个坑是去重逻辑非常绕。如果数组里有重复元素交换法产生重复排列的根本原因在于同一层里把两个相同的值换到index位置得到的结果是一样的。有人会用while判断从 index 到 i 之间有没有出现过相同的元素但这个判断写起来很容易出边界问题不如标记数组法直观。所以带重复元素的全排列我基本不用交换法。注意交换法里那句换回来必须和换过去严格对应。有人图省事写成了nums[index], nums[i] nums[i], nums[index]只写一次递归完就不管了结果数组越走越乱答案要么变少要么直接错乱。5. 去重数组里有重复元素怎么办5.1 重复排列是怎么冒出来的先看一个具体的例子数组[1,1,2]。如果直接用标记数组法会得到六组答案[1,1,2]、[1,2,1]、[1,1,2]、[1,2,1]、[2,1,1]、[2,1,1]。你会发现每两组是重复的正确答案只有三组。重复的根源在于数组里有两个 1它们的值是相同的但下标不同。标记数组法判断的是下标有没有被用过不判断值是不是重复。所以在第一层选择时选第一个 1 和选第二个 1会被当成两种不同的选择往下递归自然就产生了结构相同的结果。想解决它思路也很直接在同一层决策里如果某个值已经被尝试过了就不要再用相同的值去试第二次。5.2 排序 used 判断的两种写法具体实现之前第一步是给数组排序。排序的目的是让相同的元素挨在一起这样才好判断当前元素是不是和前面那个重复了。def permuteUnique(nums): 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这一版和基础版的区别只多了一行if但这一行的逻辑值得抠一抠。它的意思是如果当前元素和它前一个位置的值相同而且前一个位置在这个时刻没有被使用那就跳过当前这个。5.3 为什么是 not used[i-1]not used[i - 1]这个条件是最难理解的地方我换个说法解释。used[i-1] True意味着什么意味着前一个相同的值已经在当前这条路径上了也就是它在树的上层被选了。这种情况下两个相同的元素处在不同的层级说明它们的相对位置已经定下来了不会产生重复排列应该允许。used[i-1] False意味着什么意味着前一个相同的值在这一层还没被选而你现在准备选当前这个值。也就是说同一层里有两个值相同的位置都摆在面前你选了后面的那个。这时候就该拦住——因为如果你先选了前面的第一次循环时同样能得到一批结果现在选后面的第二次循环时得到的结果跟前一次完全一样纯属重复劳动。一句话总结同一层里值相同的元素只允许用第一个后面的全部跳过不同层级的相同值不受影响。5.4 cnt 数组法的另一种思路除了用排序加判断还有一种不排序的做法先用哈希表统计每个值出现了几次递归时按值来枚举而不是按下标。这样一来相同值只对应哈希表里的一个键天然就不会重复。from collections import Counter def permuteUnique(nums): counter Counter(nums) n len(nums) path [] res [] def dfs(): if len(path) n: res.append(path[:]) return for key in counter: if counter[key] 0: continue counter[key] - 1 path.append(key) dfs() path.pop() counter[key] 1 dfs() return res这版的代码更短逻辑上更贴合枚举值而不是枚举位置的直觉也不用额外排序省了 O(n log n) 的时间。代价是多了一个哈希表空间上略吃亏。两种写法没有绝对优劣看你习惯哪种思维。我个人在面试里更倾向写排序版本因为它更通用稍微改一改就能套到组合、子集等其他题型上。6. 字典序与 next_permutation6.1 字典序到底是什么字典序就是查字典时的排序规则从左往右逐位比较第一位小的排在前面第一位相同就比第二位依次类推。[1,2,3]的六种排列按字典序从小到大排就是[1,2,3]、[1,3,2]、[2,1,3]、[2,3,1]、[3,1,2]、[3,2,1]。很多题目会要求按字典序输出比如果汁排列或者组合类的题标准解法都是先排序再用回溯因为从下标 0 开始顺序扫描的标记数组法天然就产生字典序结果。这一点值得记住省得你额外写排序逻辑。6.2 手写 next_permutation 的四步法有一类题目问的是给定一个排列求按字典序排在它后面的下一个排列且要求原地修改。这道题有个 O(n) 的经典解法思路分四步从右往左找第一个下降点即满足nums[i] nums[i1]的最大下标 i。如果找不到说明整个数组是降序的已经是最后一个排列直接反转整个数组回到第一个。从右往左找第一个大于nums[i]的元素nums[j]交换nums[i]和nums[j]。把 i 后面的部分反转让它变成升序也就是最小的排列。void nextPermutation(vectorint nums) { int i nums.size() - 2; // 第一步找下降点 while (i 0 nums[i] nums[i 1]) --i; if (i 0) { int j nums.size() - 1; // 第三步从右往左找第一个比 nums[i] 大的 while (nums[j] nums[i]) --j; swap(nums[i], nums[j]); } // 第四步反转后半段 reverse(nums.begin() i 1, nums.end()); }这套算法为什么成立直觉上从右往左找下降点是在找排列里还能再变大一点的位置。下降点右边一定是降序的也就是说右边已经是那个位置能组成的最大排列了所以必须往前动一位。交换完之后右边还是降序的反转一下变成升序得到的就是最小的补全方案整体也就成了当前的下一个排列。6.3 第k个排列数学法一步到位另一道很有意思的题是第 k 个排列。暴力做法是生成所有排列然后取第 k 个但 n 稍微大一点就废了。实际上这道题可以用数学方法直接构造不用搜索。原理是这样的第一个位置由(k-1) / (n-1)!决定取第几个元素确定第一位之后把 k 更新为(k-1) % (n-1)!剩下的位置以此类推。import math def getPermutation(n, k): nums [str(i) for i in range(1, n 1)] k - 1 # 转成 0 索引 res [] while n 0: n - 1 fact math.factorial(n) idx k // fact # 当前位选第几个 k % fact # 更新 k res.append(nums.pop(idx)) return .join(res)举个例子n3k3。先算fact 2! 2idx 2 // 2 1说明第一位取索引1的元素也就是2, 对的因为字典序第三组是[2,1,3]第一位确实是2。把2从候选里拿掉k 2 % 2 0。接下来fact 1! 1idx 0 // 1 0第二位取剩下的第一个也就是1。最后剩3第三位就是3。结果213和预期一致。这道题的妙处在于它把枚举变成了计算把复杂度从 O(n! × n) 压到了 O(n²) 甚至 O(n)。能写出这一版面试官对你的评价会明显上一个台阶。7. 复杂度分析与剪枝7.1 时间复杂度到底怎么算全排列的时间复杂度是 O(n × n!)。这个n!好理解叶子节点一共 n! 个。那前面乘的 n 是哪来的来自路径的拷贝。每走到一个叶子节点都要把长度为 n 的path复制一份存进结果里这一次拷贝是 O(n)。所以总时间等于叶子数乘以每次拷贝的开销也就是 O(n × n!)。另外树内部节点的总数也在同一个量级循环里的判断和递归调用加起来不会超过这个上界。这个分析有个实际意义如果你的解法时间复杂度还是 O(n × n!)但跑的用例超时了说明问题不在算法复杂度而在于常数太大比如你在循环里做了不必要的拷贝、字符串拼接或者哈希查表。优化方向应该是减少常数不是换算法。7.2 空间复杂度不计结果集的话递归栈的深度是 n每一层要保存循环变量和局部状态所以空间是 O(n)。标记数组法是 O(n) 栈加 O(n) 的used数组整体还是 O(n)。交换法省掉了used栈深度同样是 n。如果把结果集算进去那就是 O(n × n!)因为一共 n! 个排列每个长度 n。这个量级在 n10 的时候就是三千六百万个整数内存早就爆了。所以题目通常不会要求你返回所有排列或者会把 n 控制得很小。7.3 排列题里的剪枝场景纯粹的生成所有排列没什么可剪的因为每个叶子都是合法答案。但排列类的变体就大有可为剪枝是拉开解法水平差距的关键。第一种是前面讲过的同层去重剪枝跳过同层重复值。第二种是约束剪枝典型的是 N皇后问题虽然不是全排列但思想一脉相承——在放置每一个皇后的时候都检查是否和已有的冲突冲突就直接返回不再往下递归。这一剪能把原本 n^n 的搜索空间压到接近 n! 的量级。第三种是可行性剪枝比如要求排列满足某种相邻约束一旦某一步已经违反约束就提前返回。我踩过的一个坑是剪枝条件写得太宽。有一次为了优化我把一个看起来不可能成立的条件加进去提前返回结果把合法答案也剪掉了跑出来的结果少了好几组。剪枝的前提是数学上严格证明被剪掉的分支里绝对不可能有答案只要有一丝不确定宁可多算一点也别乱剪。8. 常见问题排查速查表刷全排列的时候绝大多数错误都集中在几个固定位置。我整理了一张表照着对号入座基本能解决九成问题现象大概率原因修复方式结果全是空数组存结果时没做深拷贝改成path[:]或new ArrayList(path)答案数量偏少撤销逻辑漏了或者没对称检查pop和标记还原是否成对出现答案数量偏多去重的剪枝条件写反了确认是not used[i-1]而不是used[i-1]答案重复但数量对没排序就去重先sort()再判断相邻元素Java 版本结果错乱remove(int)和remove(Object)混用用remove(path.size()-1)按下标删程序超时哈希表统计版本常数太大换排序加标记数组版本递归栈溢出n 太大或者终止条件写错检查终止条件是否真的能命中除了表里的这些还有个隐蔽的坑数组里出现 0 或者负数时如果用到了排序后比较相邻元素的去重逻辑注意不要用nums[i] nums[i-1] 1之类的连环判断老老实实用相等判断不然负数会出错。9. 面试现场的一些实战体会写了这么多最后聊几句偏经验层面的东西这部分在大厂面经里一般看不到但确实管用。第一个体会是面试时先写标记数组法别一上来就炫技写交换法。标记数组法的正确率最高面试官读代码最顺你在讲解的时候也容易把选择、递归、撤销三步说清楚。等面试官追问能不能省点空间的时候再顺势说出交换法的思路这时候加分效果最好。反过来如果你直接写交换法面试官很可能先问你如果数组有重复元素这版还能用吗一句话就把你问住了。第二个体会是主动说出复杂度。很多人写完代码就等着面试官问其实你可以在写完之后主动补一句时间复杂度是 O(n × n!)主要开销在叶子节点的拷贝上。这句话一出来面试官就知道你不是背模板的是真的理解这个算法的开销在哪。第三个体会是去重那一行条件一定要能讲清楚not used[i-1]的来龙去脉。这是全排列系列最能区分水平的地方。我见过不少人能把代码默写出来但被问到为什么后面加个 not就答不上来只能含糊说记住是这样写的。答不出这一点前面的代码写得多漂亮都白搭。第四个实操层面的小建议刷题的时候别只刷一道就过。建议按照基础全排列 → 含重复元素 → 下一个排列 → 第k个排列这个顺序四道连着做一遍每道都手写不靠模板写完对拍一遍结果。这一轮下来回溯的框架基本就刻在脑子里了以后再遇到子集、组合、分割回文串之类的题你会发现都是同一套模具换不同的填料而已。至于后面还能怎么扩展其实路子挺多。一个是把全排列和剪枝结合得更深比如带顺序约束的调度问题一个是把它当成搜索框架的入门跳板往八皇后、数独、单词搜索这些经典题上延伸。这些题目的骨架都能从今天这套代码里长出来你现在把根扎稳了后面往上搭什么都不会晃。