1. 全排列到底在排列什么从密码锁说起先抛一个场景你手里有个三位数的行李箱密码锁每一位可以从0到9随便设问总共有多少种可能的密码组合答案是10×10×101000种。这个把每个位置上的可能值都试一遍的思路就是排列组合最朴素的直觉来源。而全排列问题要更严格一点——不是每一位独立选数字而是给定一组互不相同的元素把它们所有可能的顺序都列出来一个不多一个不少。打个比方你手里有三张牌A、B、C。所谓全排列就是把这三张牌摆成一排问有多少种不同的摆法。答案是6种ABC、ACB、BAC、BCA、CAB、CBA。如果牌是4张就是24种5张是120种。数学上n个不同元素的全排列总数是n的阶乘记作n!。这个增长速度有多离谱10!已经是362880013!就超过了62亿。所以全排列问题的核心难点从来不是会不会算而是当n稍微大一点暴力枚举就撑不住了你必须理解它的递归结构、剪枝逻辑和去重机制才能在有限资源下把问题解出来。我在带新人做算法练习时发现一个特别普遍的现象很多人能背出回溯三部曲的模板代码但一遇到有重复元素怎么去重为什么要先排序剪枝到底剪掉了什么就卡壳。这说明他们只记住了代码的形状没有真正理解全排列的搜索树长什么样。这篇文章我想把这件事彻底讲透——从最基础的交换法、回溯法到含重复元素的去重优化再到实际工程里遇到性能瓶颈时该怎么砍全部用图和例子说清楚。这篇文章适合三类人正在啃数据结构与算法基础的同学、准备技术面试需要手写全排列的求职者以及在实际项目里需要做排列枚举比如任务调度、路径规划、测试用例生成的开发者。不管你是刚入门还是想回头补基础下面这些内容我都尽量用最直白的方式展开需要的地方会配示意图和可直接运行的代码。2. 把排列过程画成一棵树理解回溯法的骨架2.1 为什么全排列天然适合用递归描述要理解全排列最好的方式是在脑子里长出一棵决策树。还是拿ABC三张牌举例想象你有一个空盒子要往里依次放牌。第一步你问自己第一个位置放谁有三种选择放A、放B、放C。这就在树根下分出了三条枝。第二步假设第一个位置放了A现在手里还剩B和C第二个位置可以放B或C于是A这条枝下又分出两条。第三步只剩最后一张牌没得选只能放它。走到这里一个完整的排列就诞生了。把这棵树画出来根节点是空第一层3个节点A、B、C第二层每个节点下挂2个子节点第三层每个节点下挂1个。总叶子数 3×2×1 6正好是3!。这棵树的每一条从根到叶子的路径就对应一个完整的排列。这里就引出了递归的本质求n个元素的全排列这个问题可以拆解成依次固定第一个元素再求剩下n-1个元素的全排列。当只剩下一个元素时排列就只有它自己递归到底开始返回。这个自己调用自己、层层缩小问题规模的结构正是递归最典型的应用场景。很多教程一上来就甩代码我觉得顺序反了。你得先在脑子里把这棵树看清楚代码只不过是把走路的过程翻译成计算机语言。树看懂了代码就是自然流淌出来的而不是背下来的。2.2 回溯走过去还要退回来光有递归还不够全排列的另一个灵魂是回溯。什么叫回溯用走迷宫打比方你走到一个岔路口选了一条路往前走发现是死胡同于是退回到刚才那个岔路口换另一条路再走。这个退回来重新选的动作就是回溯。对应到全排列的代码里回溯体现在选择—递归—撤销选择这三步。我们还是用位置填充的视角来写def permute(nums): result [] path [] used [False] * len(nums) def backtrack(): # 终止条件path里已经装满了所有元素 if len(path) len(nums): result.append(path[:]) # 注意要拷贝不能直接append(path) return for i in range(len(nums)): if used[i]: continue # 已经在path里的元素跳过 used[i] True # 做选择 path.append(nums[i]) backtrack() # 进入下一层决策 path.pop() # 撤销选择回溯 used[i] False # 撤销标记 backtrack() return result这段代码里最容易被忽视、也最容易写错的地方是result.append(path[:])这个拷贝。新手常见的bug是直接写result.append(path)结果最后输出一堆空列表或者全是同一个结果。原因在于path是个引用它在整个递归过程中被反复修改如果你存的是引用那么等到所有递归结束时path已经被清空了因为每次都pop到底你拿到的自然是空的。path[:]相当于给当前的path拍了一张快照存进结果里。这个坑我当年踩过不止一次面试时如果写错这一行基本就凉了。另一个细节是used数组的作用。它记录哪些元素已经在当前路径里被用过了避免同一个元素在一个排列里出现两次。这是最直观的状态标记法理解成本最低也是我最推荐新手先掌握的方式。2.3 交换法另一种更省空间的写法除了用used数组标记还有一种更原地的写法叫交换法。它的思路是不去额外记录谁被用了而是通过交换位置让已经确定的位置和还没确定的位置自然分开。具体操作是把数组的第start位和它后面的每一位依次交换交换后递归处理start1开始的部分递归回来后再把两个位置换回去这就是回溯。def permute_swap(nums): result [] def backtrack(start): if start len(nums) - 1: result.append(nums[:]) return for i in range(start, len(nums)): nums[start], nums[i] nums[i], nums[start] # 交换相当于选第i个放到start位 backtrack(start 1) nums[start], nums[i] nums[i], nums[start] # 换回来回溯 backtrack(0) return result交换法的精妙之处在于start左边的元素代表已经摆好的前几把牌start及右边代表还没用的牌。每次把右边某个牌换到start位置就等于宣布这张牌就放这儿了然后去处理后面的。递归回来后换回去数组恢复原样好让start位置能尝试下一张牌。这两种写法的对比我整理了一张表对比维度used标记法交换法空间开销额外O(n)的used数组和path原地操作几乎零额外空间结果顺序按原数组顺序输出顺序会乱不保证字典序是否修改原数组不修改会修改但递归后恢复是否易于去重非常容易配合排序去重较麻烦适合场景含重复元素、需要字典序元素互不相同、追求省空间我个人在实际做题时的选择是如果题目要求结果按字典序或者元素可能有重复一律用used标记法如果只是简单求排列且n很小交换法写起来更快。这个取舍后面讲到去重时还会再展开。3. 从n个里挑m个组合和排列的区别别搞混3.1 排列讲顺序组合不讲顺序很多人初学时会混淆排列和组合。用一句话区分排列在乎顺序组合不在乎顺序。还是ABC三张牌取两张出来——AB和BA在排列里是两个不同的结果在组合里是同一个。这个区别看起来小落到代码上却是两套完全不同的剪枝逻辑。组合问题里为了避免选了A再选B和选了B再选A被重复计算我们通常会引入一个start参数规定只能从当前元素往后选保证每个组合只会被枚举一次。def combine(n, k): result [] path [] def backtrack(start): if len(path) k: result.append(path[:]) return # 剪枝如果剩下的元素不够凑满k个直接停止 for i in range(start, n - (k - len(path)) 2): path.append(i) backtrack(i 1) # 注意是i1保证不重复选前面的 path.pop() backtrack(1) return result注意那个range的上界——n - (k - len(path)) 2。这就是剪枝的一个经典例子。假设n5、k3当前path里已经有0个元素那i最多只能到3因为如果从4开始选后面只剩5一个数凑不满3个。把上界提前收紧能省掉大量注定无解的分支。3.2 剪枝的本质是提前判断死路我第一次真正理解剪枝是画搜索树的时候发现很多分支走到一半就已经注定不可能得到合法答案了但我们还在傻乎乎地往下走。剪枝就是提前发现这些死路直接砍掉不让程序白费力气。生活里到处是剪枝你出门旅游如果发现飞机已经误点赶不上了就不会还傻乎乎地打车去机场——这就是剪枝。算法里的剪枝判断依据通常有两种一是剩余资源不够了像上面的组合问题二是再往下走一定会重复或违反约束这是排列去重的核心。在全排列问题上剪枝用得最狠的地方就是处理重复元素这块特别容易出错我下面单独开一节讲。4. 有重复元素的全排列去重为什么必须先排序4.1 重复元素带来的重复排列假设现在不是ABC而是A、A、B三个元素让你求全排列。如果你直接套用前面的used标记法会得到6个结果AAB、ABA、AAB、ABA、BAA、BAA——你会发现有一半是重复的。原因是两个A被当成了不同的元素交换它们的位置得到了看起来一样的排列。正确的答案应该只有3个AAB、ABA、BAA。那怎么让程序自动过滤掉重复的呢这就引出了全排列问题里最经典也最容易写错的一步先排序再在递归时加一个去重判断。4.2 去重条件到底怎么写主流解法是先把数组排序让相同的元素挨在一起然后在每一层循环里如果发现当前元素和前一个元素相同且前一个元素没被使用过就跳过当前元素。def permute_unique(nums): nums.sort() # 关键第一步排序 result [] path [] used [False] * len(nums) def backtrack(): if len(path) len(nums): result.append(path[:]) return for i in range(len(nums)): 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]) backtrack() path.pop() used[i] False backtrack() return result这个not used[i-1]的条件是所有人第一次看都会懵的地方。我给你翻译成人话同一层里如果有两个相同的数比如两个A那我们规定只允许第一个A先被用第二个A在这一层不许打头。为什么因为第二个A打头产生的所有排列第一个A打头时已经全产生过了重复了。为什么要强调在这一层因为层是按递归深度分的。同一层的循环是在给同一个位置选元素选哪个A本质上没区别所以要限制。但不同层不同位置是可以都选A的比如第一个位置选A第二个位置再选A这是合法的。我用一个具体的例子帮你把逻辑走一遍。nums [1,1,2]排序后还是[1,1,2]。第一层位置0i0选第一个1正常递归。i1时nums[1]nums[0]且used[0]在这层还没被用过刚递归回来已经撤销了所以跳过。这就避免了第二个1在位置0打头。走到i2选2也正常递归。这样跑下来最终结果刚好是[1,1,2]、[1,2,1]、[2,1,1]三个一个不多一个不少。4.3 常见错误把not used[i-1]写反了我见过太多人把去重条件写成used[i-1]丢掉那个not结果得到的要么是重复结果没去掉要么是合法结果被误删。这两个条件带来的输出数量往往一样但含义完全不同。not used[i-1]是树层去重同一层里相同的不重复选而used[i-1]是树枝去重同一条路径上不去重。对全排列来说我们要的是前者。判断方法很简单你把代码跑一遍看输出结果对不对。如果结果里有重复或者数量少于预期就回头检查这个条件。另外排序这一步绝对不能省——不排序的话相同的元素不挨在一起去重判断nums[i] nums[i-1]根本不成立去重直接失效。这是另一个高频错误点。5. 性能瓶颈在哪里全排列的时空复杂度与工程优化5.1 复杂度到底怎么算先说时间复杂度。n个元素的全排列有n!个结果而每生成一个结果至少要做n次操作填充n个位置所以光输出结果这一项就是O(n × n!)。再加上回溯过程本身要遍历搜索树的所有节点总的时间复杂度是O(n × n!)。这个量级有多恐怖n10时是3600万左右的操作n12时接近6亿n13直接上到80亿量级的操作普通机器就扛不住了。空间复杂度分两部分递归栈的深度是O(n)存放结果的空间是O(n × n!)因为结果本身就有n!个每个长度n。值得注意的是如果题目只要求输出结果的总数或者找特定条件下的答案而不需要把所有结果都存下来那你可以省掉O(n × n!)的结果空间只保留递归栈的O(n)。这里给一张不同n值下的规模对照让你对全排列为什么会爆有个量化的感知n排列总数 n!大致操作量 n×n!参考量级3618瞬间5120600瞬间84032032万毫秒级1036288003600万秒级1247900160057亿需要优化13622702080080亿别想了换方法5.2 当n变大时到底该砍哪里面对全排列的爆炸式增长工程上有几条思路第一能用贪心或动态规划就别硬枚举。很多看似需要全排列的问题其实有更高效的解法。比如旅行商问题暴力解法是n!的排列枚举但小规模下可以用状态压缩DP降到O(2^n × n²)。我做过一个任务调度的项目一开始写的是全排列枚举所有任务顺序求最优n15时直接卡死后来改成状态压缩DP同样的n跑得飞快。这个教训是先想清楚问题的最优结构再决定要不要用排列。第二善用剪枝把死枝砍掉。如果问题带约束比如某两个元素不能相邻在递归过程中提前判断不合法的分支直接返回能省掉大量无效枚举。这就是回溯 剪枝的组合拳也是回溯算法真正的威力所在。第三用迭代而非递归来避免栈溢出。n比较大时递归深度会带来栈溢出的风险。可以手动用栈模拟递归过程虽然代码复杂但能撑更大的n。不过说实话全排列真到了需要用迭代的程度通常意味着你该换算法了。第四只在必要时生成完整结果。如果只需要是否存在满足条件的排列或第k个排列完全没必要把所有排列都生成出来。比如下一个排列问题可以用字典序算法直接推导第k个排列可以用数学方法定位完全避开暴力枚举。5.3 字典序排列不枚举也能求下一个这里额外讲一个重要技巧——按字典序生成下一个排列。有时候你不需要所有排列只需要当前排列的下一个。这个算法很优雅从右往左找第一个升序的相邻对即nums[i] nums[i1]记下i。再从右往左找第一个大于nums[i]的元素nums[j]。交换i和j。把i1到末尾的部分反转让它变成升序升序是所有排列里最小的。def next_permutation(nums): i len(nums) - 2 while i 0 and nums[i] nums[i1]: i - 1 if i 0: j len(nums) - 1 while nums[j] nums[i]: j - 1 nums[i], nums[j] nums[j], nums[i] nums[i1:] reversed(nums[i1:]) return nums这个算法的时间复杂度是O(n)空间是O(1)比全排列枚举高效太多。实际面试里下一个排列是高频题能写出这个的人不多但理解了字典序的本质就很容易记住。6. 面试和实战里的全排列那些文档不会告诉你的细节6.1 面试时的常见追问方向我参加过不少算法面试也帮人做过模拟面试发现全排列这道题面试官最爱追问三个方向一是去重判断为什么有效。很多人能背出nums[i] nums[i-1] and not used[i-1]但被追问为什么不是used[i-1]时答不上来。你要能说清楚同一层里相同的数只允许第一个出场这个逻辑最好能现场画出搜索树解释。二是时间复杂度。面试官希望听到O(n × n!)并且能解释清楚为什么是乘不是加。很多人只会说n的阶乘就不完整了。三是能不能优化。这时候你可以提剪枝、提字典序、提如果只需要第k个用数学方法这些思路展现你不仅会写模板还懂工程取舍。6.2 一个真实的踩坑记录我印象最深的一次翻车在线笔试时遇到全排列含重复元素我图省事用了交换法而且没有排序就去重。结果第一个测试用例过了第二个用例带重复元素直接栽了。交换法去重的正确写法其实也能做但需要额外判断start位到i位之间是否出现过和nums[i]相等的元素比used标记法麻烦得多。后来我总结出一个经验只要题目涉及去重立刻切换到used标记法 先排序。这个组合拳几乎不会出错代码结构也清晰。别为了省那点空间去用交换法在带重复元素的场景下可读性和正确性远比省内存重要。还有一个细节path[:]的拷贝一定要做而且要做深拷贝的判断。如果nums里存的是可变对象比如列表path[:]只是浅拷贝结果里存的还是引用同样会出问题。这种情况要么存结构化的值副本要么用deepcopy。这个坑比较隐蔽处理复杂数据时才会遇到。6.3 全排列思维在其他领域的迁移全排列不只是算法题它的思想在很多地方能迁移用上测试用例生成要覆盖多种参数组合用排列枚举找出所有可能的参数顺序。密码破解与安全分析理解排列空间的大小才知道为什么长密码更安全每增加一位搜索空间乘以字符集大小。任务调度在任务数量很少时枚举所有执行顺序找最省时间的那个。路径规划小规模下枚举访问顺序来求解配合剪枝去掉明显更差的分支。数独与拼图求解本质上都是带约束的排列搜索靠剪枝高效求解。我在做一个自动化测试框架时就借用了全排列的思路来生成API调用顺序的测试矩阵。当时第一版直接暴力枚举参数稍微多一点就跑不动后来加了只枚举长度不超过3的子排列和已知不兼容的组合提前剪掉两条剪枝规则效率提升了好几倍。全排列的价值不在于那几行代码而在于它背后搜索 剪枝 去重的通用思维框架这个框架你一旦掌握遇到任何组合类搜索问题都能往上套。最后再分享一个我自己练全排列的小方法不要光看代码拿张纸手动把4个元素ABCD的搜索树画一遍边画边标记这里为什么剪枝这里为什么去重。画完一遍再合上纸默写代码你会发现那些曾经莫名其妙的条件突然都变得理所当然。这比刷十道类似的题都管用。