早几年刷题的时候我一度把回溯算法当成深搜的套壳每次看到树的题目都绕道走直到被LeetCode 46题全排列迎面打了一拳才发现回溯其实没那么玄乎。这道题给了一个不含重复数字的数组要求返回所有可能的全排列比如输入[1,2,3]输出8种排列中的任意顺序均可。很多教程把它当作回溯算法的入门模板题但真正上手之后卡住的人一大半卡在为什么递归完之后还要把状态还原回去另一半卡在为什么最终结果要存path[:]而不是path。这篇文章就把这道题掰开揉碎讲清楚顺便把去重、交换法、复杂度、变体都串起来帮你一次性把排列类问题看通透。1. 全排列题面拆解n个小球放进n个格子全排列的本质是把n个不同元素按不同顺序排列。数学上我们知道结果数是n!但代码层面怎么把每一种排列都生成出来才是这道题的核心。题面一般是这样描述给定一个不含重复数字的数组nums返回所有可能的全排列。这里不含重复数字是第46题的关键前提因为一旦有重复数字结果中相同的排列会被多次输出那就要用第47题的进阶去重思路这个我后面专门讲。很多人上手就直接写递归写到一半发现不知道该怎么记住已经用过的数字。实际上全排列可以理解成这样一个过程你有三个空位第一个空位可以从3个数字里选一个第二个空位从剩下2个里选一个第三个空位只能选剩下的那一个。这个决策过程画出来就是一棵树每个从根到叶子的路径就是一个排列。递归就是在深度优先地遍历这棵树。用[1,2,3]举例树的根是空列表第一层有三个分支选1、选2、选3。比如第一步选了1接下来第二层只能从2和3里选如果第二步选了2第三步就只能选3于是得到排列[1,2,3]。然后你需要退回到第二步还没选的状态改选3得到[1,3,2]。这个退回的动作在代码里就是撤销选择也是回溯算法名字中回字的由来。我在实际刷题时发现只要能把递归树的形态在脑子里画出来代码几乎不会写错。这也是为什么我在给同事讲这道题时永远先画树再讲代码而不是直接扔一段制式模板。下面的几个章节我会从递归树出发逐步拆解标准模板、两种实现方案、去重扩展和性能问题。2. 回溯算法的核心流程选择、递归、撤销2.1 三步走模板全排列的标准答案刷过一段题之后你会发现回溯算法有一个高度统一的模板结构在每一层递归中从候选集里选一个元素加入当前路径然后递归进入下一层递归返回后再把该元素从路径中移除同时恢复它的可用状态。这个模板套在全排列上几乎是教科书级别的应用。下面是Python的标准写法def permute(nums): res [] path [] used [False] * len(nums) def backtrack(): # 递归终止path 长度已经等于 nums 长度说明收集完一个排列 if len(path) len(nums): res.append(path[:]) return # 每一层都从头遍历所有元素跳过已使用的 for i in range(len(nums)): if used[i]: continue # 选择 used[i] True path.append(nums[i]) # 进入下一层 backtrack() # 撤销选择 path.pop() used[i] False backtrack() return res关键就四个动作检查终止条件、遍历候选元素、做选择进入下一层、撤销选择恢复现场。used数组记录了哪些索引位置已经被当前路径占用这是排列问题和组合问题最本质的差异点。组合问题中[1,2]和[2,1]是同一个组合所以需要用一个start参数让遍历方向单向流动而排列问题中它们是两个不同的结果因此每一层递归都必须从0开始重新扫描所有元素。2.2 撤销选择为什么是灵魂我曾经见过有初学者把撤销步骤去掉只保留used[i] True和path.append(nums[i])然后发现结果集里只有第一个全排列后面全是空列表或者越来越长的路径。原因很简单如果你不撤销path只会不停追加元素永远不会回到上一层决策时的状态。递归的本质是用栈保存函数调用但是path和used是共享状态不会随着函数返回而自动恢复。打个比方你在一个迷宫里走走到死胡同后要退回上一个岔路口同时把沿途做过的标记全部擦掉否则那些标记会影响你后面的判断。撤销used[i] False就是擦掉该位置已被占用的标记path.pop()则是从当前路径中移除这个元素让岔路口重新变成未选择的状态。没有这两个操作搜索就变成了一条道走到黑根本不可能遍历整棵树。这段逻辑也是面试官最常追着问的点。你最好能用自己的话讲清楚为什么递归到叶子时需要还原还原的本质是让不同分支可以共享同一份状态数组。2.3 结果收集时为什么要存path副本看看上面代码里的res.append(path[:])这里如果用res.append(path)最终返回的结果会是一堆一模一样的列表里面全是[1,2,3]之类的最终状态。原因在于path是一个可变列表它指向的内存空间在后续递归中还会被反复修改。res里保存的不是当时的值而是对象的引用。等所有递归结束path回到了空列表状态你看到的res自然也就是一堆空列表。正确做法是拷贝一份当前状态的快照。Python里写path[:]即可等价于list(path)。在Java/C里需要显式new ArrayList(path)或vectorint(path)。我早期在这上面栽过跟头调试半天排除了递归逻辑问题最后才意识到是引用拷贝的锅。面试时候答这道题一定要主动说明这一步存在的意义能给你加分不少。3. used数组与交换法全排列的两种主流实现3.1 为什么排列问题必须从头遍历组合类问题子集、组合总和、分割回文串常用start参数来控制下一层递归的起点比如选了i之后下一层从i1开始这样就不会回头选到之前的元素避免了组合重复。但排列问题恰恰需要回头因为[1,2,3]和[1,3,2]是两个不同的排列第二层选了2之后第三层还要能回头选3反之如果你用start去限制起点一旦第一层选了1第二层只能从2开始根本选不到1这样生成的排列数量是少很多的。所以排列问题的核心机制是每一层递归都重新从头到尾遍历数组配合used数组跳过已经被当前路径使用过的元素。这样既能保证每个排列中元素不重复又能保留所有顺序可能性。有的初学者会把used数组理解成简单的访问标记忽略了它是共享状态并且需要及时恢复这一点前面已经强调过但这里再提一次因为它是和组合问题最显著的差异。3.2 交换法的思路与代码对比不用used数组也能实现全排列那就是交换法。核心思想我们不需要额外标记某个元素是否使用过只需要把当前递归层负责的位置start轮流交换成数组里每一个还没固定位置的元素即可。每当start走到数组末尾当前的nums就是一个成品排列。def permute(nums): res [] def backtrack(start): if start len(nums): res.append(nums[:]) return for i in range(start, len(nums)): # 选择把 nums[i] 放到 start 位置 nums[start], nums[i] nums[i], nums[start] # 递归处理下一个位置 backtrack(start 1) # 撤销交换 nums[start], nums[i] nums[i], nums[start] backtrack(0) return res这段代码每次递归都把start位置的元素换成后面所有可能的选择递归的下一个位置是start1。它不需要额外的used数组也不需要额外的path列表直接在原数组上操作省了一定的空间。但代价是修改了传入的nums如果你在递归结束后还要继续使用原始数组需要小心保存副本。而且交换法是以位置为线索在排列元素直觉上不太容易扩展到从候选集中挑选的广义回溯问题。实际面试中我推荐优先掌握used数组版本理解透之后再看交换法作为补充。3.3 两种方案的性能与适用场景对比从时间复杂度看两者都是O(n!)量级因为本质上都在遍历同一棵递归树。但交换法在空间上少了used布尔数组和path列表而且不需要在递归中反复做append和pop通常在常数上会快一些。在我的本机测试里n9时交换法大概比used法快20%左右但这并不重要因为全排列题目的真实瓶颈永远是指数爆炸再优化的常数也救不了n11。used数组法的优势在于通用性强。比如后面讲到的含有重复数字的全排列第47题、组合总和、单词搜索等一大批回溯题目都是在这个骨架上增加剪枝条件。交换法则比较适合处理纯排列、且允许原地修改的场景。还有一个细节递归函数中如果直接使用外部nums进行交换需要注意Python的默认参数和闭包修改问题如果nums是全局变量倒是无所谓如果通过参数传入记得在递归前自己处理好可变对象的拷贝语义。4. 延伸一步有重复数字时如何剪枝4.1 先排序再回溯让重复元素相邻出现LeetCode第46题说数组不含重复数字但面试官最常见的追问就是如果数组里有重复数字比如[1,1,2]怎么保证结果不重复这其实就是第47题。最简单的去重思路是先把nums排序让重复元素相邻然后在使用时跳过那些会造成重复分支的元素。排序的意义在于把是否重复的判断从O(n)缩小到只看前一个元素而且能保证相同值的元素在每一轮选择中只被第一个可用的那一个代表。以[1,1,2]为例如果不做任何去重标准回溯会生成[1,1,2]、[1,2,1]、[1,1,2]、[1,2,1]、[2,1,1]、[2,1,1]一共6个结果其中有大量重复项。去重后应该只输出3个[1,1,2]、[1,2,1]、[2,1,1]。4.2 核心剪枝条件为什么是not used[i-1]在排序的基础上我们在每一层遍历时加一行判断if i 0 and nums[i] nums[i-1] and not used[i-1]: continue这行代码的意思是如果当前元素和前一个元素值相等并且前一个元素还没有被使用过那么当前的这一分支应当剪掉。很多人不理解为什么是not used[i-1]这里我展开讲。想象一下nums [1,1,2]第一个1和第二个1是等价的。回溯时如果允许第二个1在第一个1之前被选中就会产生和另一个分支一模一样的排列。我们的策略是让相同元素按照它们在数组中的顺序依次被选择不允许跳过前一个重复元素直接选后一个。所以当遍历到第二个1时如果前一个1还没进入当前路径说明我们正在尝试一个逆序的选择这个分支应该跳过。反过来如果写成used[i-1]会怎样那表示只有在当前路径已经使用了前一个1时才跳过第二个1。这会导致整个搜索过程中一个重复元素的分支被完全压制某些合法排列如[1,1,2]反而永远生成不了。这个差别很细微但写错的人非常多。我在LeetCode评论区见过不少人在这个条件上反复横跳最后靠打日志才搞明白。你可以在本地跑一遍、打印递归树对比这两种剪枝条件的区别比死记硬背管用得多。4.3 越界与递增序列的细节陷阱剪枝条件的第一个前提是i 0否则访问nums[i-1]在i0时会越界这是一个低级错误。但更隐蔽的问题是这个剪枝依赖排序后相同元素相邻这一前提所以必须先对数组执行nums.sort()。有些同学记得写剪枝却忘了排序结果拿到[1,2,1]这种数组时相同的元素相隔很远剪枝条件根本判断不出来最终依然输出重复排列。还有一种特殊情况是当数组所有元素都相同比如[1,1,1]剪枝会把大量分支砍掉只留下一条路径运行效率很高。但如果数组中有三个重复元素剪枝条件依然成立因为每层遍历时只允许重复元素中第一个未被使用的那个进入路径其余的一律跳过最终结果数符合组合数学预期n! / (k1! k2! ...)。5. 复杂度与实测表现为什么n10是分水岭5.1 时间复杂度不是简单的O(n!)标准回溯法本质上遍历了一棵排列树。第一层递归有n个分支第二层每个分支又有n-1个分支总叶子节点数就是n!。树中所有节点数接近n!的e倍依然是指数量级。有些教材说时间复杂度是O(n!)但实际上还不止每收集到一个排列我们都执行了一次res.append(path[:])这个拷贝操作要O(n)时间所以综合复杂度应该是O(n * n!)。如果使用交换法虽然少了path列表的增删或拷贝但收集结果时仍然需要nums[:]拷贝一份所以总的复杂度量级不变。有些人会纠结为什么LeetCode官方的时间复杂度写O(n * n!)而不是O(n!)其实就是把拷贝结果的成本算进去了。在n10时10! 3,628,800再乘以10约3600万次操作单次操作的常数如果还高跑起来已经肉眼可见地慢。到了n1212! 4.79亿乘以12就是57亿次几乎不可能在普通机器上秒级完成。所以全排列题目对n的限定通常不会超过10否则就要考虑更高级的技巧例如用迭代方式生成字典序排列或者用位运算表示状态来减少常数但量级依然无法突破。5.2 空间复杂度递归栈和结果集各算各的不考虑最终返回的结果集回溯过程本身的空间开销主要来自两部分递归栈的深度O(n)以及path列表和used数组各O(n)。所以额外空间是O(n)。很多人会把结果集算进去认为空间复杂度是O(n! * n)这其实要看题目的要求。LeetCode通常默认返回结果需要占用额外空间但分析算法本身时我们更关注递归过程中额外消耗的辅助空间。面试时候你可以先说清楚如果考虑存储所有结果那自然是O(n! * n)但如果只看递归和辅助状态空间是O(n)。这种细节反而能体现你对内存模型的敏感度。5.3 我本地的实测数据我拿Python 3.11做了一组简单的耗时测试普通回溯模板没有加任何优化只跑一次n排列总数耗时秒750400.0028403200.01693628800.1511036288001.682113991680020.37n10将将1.7秒n11已经超过20秒这个增长速度非常吓人。但作为刷题我们通常不需要跑n10的数据。如果你真的遇到全排列变体且n较大优先考虑用迭代的下一个排列法逐步生成字典序排列省掉递归栈和状态维护的开销虽然复杂度量级不变但常数能小很多。6. 全排列的经典变体字符串、字典序和排名问题6.1 字符串全排列的处理方式输入从数组变成字符串本质没有区别把字符串转成字符数组再套同样的回溯模板。但字符串题里常见的坑是如果字符重复一定要先排序再去重另外递归时直接对字符数组进行交换最后拼接成字符串时记得用.join(chars)。C选手要留意std::next_permutation这个现成函数它能直接生成字典序的全排列省不少事。但为了面试竞争力建议还是自己实现一遍回溯而不是在开口答算法时只会调库函数。还有一个细节有些面试题要求按字典序输出全排列此时used数组法的天然输出顺序其实不是严格字典序比如[1,2,3]的输出顺序和字典序不同。如果你需要字典序最稳的做法是把nums排序然后用下一个排列迭代生成或者回溯时保证每一层选择有序元素并配合一些额外约束。不过LeetCode对全排列的输出顺序一般不要求。6.2 下一个排列与全排列互补的经典题LeetCode第31题下一个排列是全排列问题的反向应用给你一个排列要求找到字典序中恰好比它大的下一个排列。核心思想是从右向左找到第一个升序对(i, i1)即nums[i] nums[i1]然后在i右侧从右向左找到第一个大于nums[i]的元素并交换最后把i右侧的部分反转成升序。这个思路如果用回溯去实现会从一个排列跳到下一个效率很低但理解它有助于你建立排列空间是有序的这一直觉也能帮你理解康托展开也就是排列排名。我当时把全排列和下一个排列连着刷感觉对排列的理解一下子立体了很多。回溯生成的是树下一个排列操作的是线性字典序两者互相印证。如果遇到给一个排列求第k个排列的问题用下一个排列循环生成k次并不优雅更好的方案是下面要讲的康托展开。6.3 从全排列到康托展开求排列的名次康托展开可以把一个排列映射成一个整数排名也可以反推出来给定排名恢复排列。它的核心是利用阶乘对于排列中第i位的数字统计在它后面还没出现过的、比它小的数字个数a_i那么排名就是1 a_1 * (n-1)! a_2 * (n-2)! ...。这个技巧在竞赛题中偶尔出现比如问[3,1,2]是[1,2,3]全排列中的第几个。这种题的思路其实可以从递归树中直观理解第一层的每个分支对应(n-1)!个排列如果你在第一层跳过了一个比当前数字小的数字排名就要加上一个(n-1)!。理解康托展开对刷全排列题有一个额外的好处你会更清楚地看到切分递归树的原理。回溯本质上是按顺序枚举每一个分支而康托展开则通过阶乘直接定位目标分支把枚举变成了跳转。虽然面试很少单独考康托展开但当面试官追问全排列还能怎么优化时你能提到这套方法会显示你对排列类问题并不是只背了一个模板。7. 调试回溯代码的几个实用技巧最后分享一些我在实际调试中总结的经验尤其是针对全排列这类回溯题。第一步打日志。如果你怀疑逻辑有误可以在递归开头打印当前path、used和递归深度例如def backtrack(): print( * len(path) fpath{path}, used{used}) ...这样打印出来的内容其实就是递归树的直观文本化表示你会清楚地看到每次选择、回溯、回溯后的状态恢复是否符合预期。从根到叶子的每一条缩进路径就是一个搜索分支。只要有一个分支的状态没有恢复日志里会一目了然。第二步从小规模数据开始验证。比如先用nums[1,2]测试排列只有两种[1,2]和[2,1]。如果这种输入都输出错了不需要看n3的复杂日志。等小规模通过后再增大到[1,2,3]数一数输出数量是否为6数量不对说明剪枝条件写错数量对但有重复则说明去重逻辑失效。第三步重点检查结果收集。如果最终res全是空列表基本可以确定没有使用path[:]如果res长度大于n!说明used或剪枝条件有问题如果res长度正好是n!但内容有重复那多半是排序/剪枝的前置条件没做全。全排列这道题虽然只算中等难度但它几乎串起了回溯算法的全部核心概念状态空间树、选择与撤销、剪枝、复杂度分析、变体转换。刷透这一题再去碰组合总和、N皇后、数独求解你会发现它们都是在同一个骨架上长出来的。这也是为什么我遇到初学者总是先推荐这一题当突破口而不是一上来就啃八皇后。你把它吃透了后面很多回溯题都能直接套用类似的思路只是状态定义和剪枝条件各不相同罢了。