1. 全排列这道题为什么是回溯算法的“敲门砖”我在刷LeetCode的过程中有一个很深的体会回溯算法这个名词看着唬人实际上你把它拆开就是“递归遍历状态空间 逐一尝试所有可能的选择”。而LeetCode第46题“全排列”恰好是理解这套逻辑最干净、最没有干扰的一题。题目描述很简单给定一个不含重复数字的数组nums返回其所有可能的全排列。比如nums [1,2,3]答案就是[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]。这题在所有“回溯”类题目里的地位相当于动态规划里的“爬楼梯”。它足够简单让你能集中精力理解回溯的骨架做选择、递归、撤销选择。几乎LeetCode热门100题、周赛里涉及排列组合的题目底层都是基于这一套模板改出来的。文章适合谁看我把话说直白一点如果你刚接触回溯看完这篇你能手写出全排列的代码并且能解释清楚每一步在干嘛。如果你已经会做这题但总觉得“会背模板、不会变通”那这篇的重点剪枝思路、去重逻辑、代码框架的迁移会对你有帮助。我不会只贴一段代码就完事而是把“为什么这么写”、“撤销这一步到底撤销了什么”、“递归里的状态是怎么传递的”这些细节全拆开揉碎讲清楚。2. 核心思路拆解状态是怎么“铺开”的2.1 从排列组合的角度理解全排列全排列的本质是把n个互不相同的元素按所有可能的顺序排成一列。高中数学里的公式是n!比如3个元素就是3! 6种。可公式只是结果代码里我们需要一种“枚举策略”。人类手动列排列时常用“固定第一位递归安排后面”的思路先固定1在第一位然后对 [2,3] 做全排列再固定2在第一位对 [1,3] 做全排列最后固定3在第一位对 [1,2] 做全排列。这个策略翻译成程序语言就是回溯。关键问题来了怎么“固定第一位”你当然可以在递归里用“标记已使用”的方式也可以直接在数组里“交换位置”来实现固定。两种手法各有千秋我后面会分别给出代码。2.2 回溯算法的结构选择、递归、撤销回溯的核心结构用一段伪代码可以表达为void backtrack(路径, 选择列表) { if (满足结束条件) { 记录当前路径; return; } for (选择 in 选择列表) { 做选择; backtrack(路径, 新的选择列表); 撤销选择; } }这段话看起来简单但很多人初学时最大的困惑是“撤销选择”到底在撤销什么我换个生活化的例子来解释。想象你要从一堆食材里挑选做一道菜的配料。你先把西红柿放进篮子接着看看还缺什么发现不行把西红柿拿出去再换黄瓜试试。“放进去——继续逛——不行就拿出来换下一个”这就是回溯。程序里的“撤销选择”就是那个“把西红柿拿出篮子”的动作。如果没有这一步你第二次尝试时篮子里还残留着西红柿最终组合就会重复或错误。放在全排列的情境里你选了1放在第一位递归处理完所有“以1开头”的排列之后必须把1从“已选择”状态里移除才能轮到2放在第一位。不撤就是死路一条。2.3 为什么用回溯而不是for循环嵌套有人可能会问全排列能不能用3层for循环写如果n固定是3当然可以三层循环暴力枚举第一位、第二位、第三位即可。但n是题目给你的参数可能大到10也可能到20你不可能写n层for循环。递归函数天然可以替代“不确定层数的循环”这就是回溯方便的地方。另外回溯比起暴力枚举还有一个隐含优势它可以配合剪枝提前排除那些明显不满足条件的分支。虽然全排列这题本身没有复杂的约束条件但它的兄弟题目——比如“全排列II”有重复元素、“组合总和”有和必须等于target的约束——都需要剪枝来避免无效递归。你先把全排列这题吃透后面那些题目就是加几行代码的事。3. 代码实现与关键细节逐行拆解3.1 最经典的写法used数组标记法我平时最推荐新手使用的版本是用一个used布尔数组来记录哪些元素已经被用过。以Python为例def permute(nums): res [] path [] n len(nums) used [False] * n def backtrack(): # 结束条件path长度等于数组长度 if len(path) n: res.append(path[:]) # 注意这里要复制不能直接append(path) return for i in range(n): if used[i]: continue # 做选择 used[i] True path.append(nums[i]) backtrack() # 撤销选择 used[i] False path.pop() backtrack() return res逐行解释一下关键点res.append(path[:])这一行是新手最容易踩的坑。如果你写成res.append(path)Python里list是引用类型后面path.pop()一执行已保存的结果也会跟着变。最终输出的就是一堆空列表[[], [], [], [], [], []]。path[:]是浅拷贝把当前路径的副本存进结果才不受后续修改影响。used[i] True和path.append(nums[i])是一对“做选择”动作used[i] False和path.pop()是一对“撤销选择”动作。它们的顺序必须严格对应撤销时不能漏掉任何一项。递归终止条件用的是len(path) n这是因为排列的长度固定为n。一旦凑满就记录结果。注意这个判断放在递归函数的最开头是最常见的回溯“出口”。3.2 另一种经典写法交换法除了used数组还有一种更贴近“数学手写思路”的写法叫交换法。它的思想是把数组分成左右两部分左边是已固定的元素右边是待排列的元素。递归层数index指向“当前要确定的位置”把index位置的元素与后面任意位置的元素交换然后递归处理index 1。def permute(nums): res [] n len(nums) def backtrack(index): if index n: res.append(nums[:]) return for i in range(index, n): # 交换相当于把nums[i]固定到index位置 nums[index], nums[i] nums[i], nums[index] backtrack(index 1) # 撤销交换 nums[index], nums[i] nums[i], nums[index] backtrack(0) return res交换法和used数组法对比起来交换法省掉了一个path数组直接在原数组上操作空间更低。交换法生成的排列顺序和used数组法不太一样。比如输入[1,2,3]交换法输出的第一个排列是[1,2,3]、[1,3,2]、[2,1,3]...而used数组法的首个排列也是[1,2,3]后续顺序也略有差异。LeetCode判题只要集合相同即可顺序无所谓。交换法的缺点是数组顺序会被修改在递归中如果还需要原数组的某种有序状态可能会出问题。全排列这种纯排列问题无所谓但某些场景下used数组法更稳。我个人建议初学先用used数组法因为它和“选择列表”的概念一一对应理解更自然等熟练之后两种都写一遍体会它们的差别。3.3 复杂度分析全排列为什么不能更快时间复杂度上全排列的状态数是n!每个状态需要拷贝一次数组O(n)所以总复杂度是O(n * n!)。空间复杂度上递归栈的深度是n如果算上结果集存储还要O(n * n!)但一般忽略输出占用的空间只讨论递归栈的话是O(n)。很多人在评论区问n!增长那么快这题是不是有更优解没有。因为题目要求你“返回所有排列”只要答案数量是n!任何算法都不可能低于这个复杂度。这类题的复杂度天花板是由“输出规模”决定的不是由算法决定的。所以刷这类题时判断一个回溯写法好不好主要看剪枝是否到位、有没有无意义的重复计算而不是指望它能突破n!的界限。4. 实操经验从全排列迁移到“全排列II”和组合问题4.1 有重复元素时怎么去重LeetCode第47题“全排列II”是全排列的直接升级版nums里可能有重复数字要求返回不重复的排列。比如[1,1,2]的全排列如果直接用第46题的代码会出现两个[1,1,2]这样的重复结果。处理手法很简单先对数组排序然后加一行剪枝。def permuteUnique(nums): res [] path [] used [False] * len(nums) nums.sort() # 排序让相同的元素相邻 def backtrack(): if len(path) len(nums): res.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() used[i] False path.pop() backtrack() return res这个剪枝条件not used[i - 1]是什么意思我拆解一下当nums[i] nums[i - 1]时说明有两个相同的元素可供选择。如果前一个相同元素尚未被使用也就是刚被撤销说明当前这次选择会重复上一次的分支应该跳过。反过来如果used[i - 1]是True说明前一个元素在当前位置已经被使用当前元素可以作为“后续位置”的重复元素正常参与递归不用剪掉。这个剪枝逻辑非常经典你在“子集II”90题、“组合总和II”40题里都会看到几乎一模一样的代码。把47题的去重原理吃透等于同时预习了三条题型的套路。4.2 组合问题的代码迁移全排列学会了“组合”其实就是一个很小的改动。LeetCode第77题“组合”要求给定n和k返回[1..n]中所有可能的k个数的组合。比如n4, k2结果是[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]。组合和排列的区别是什么排列讲顺序[1,2]和[2,1]是两种组合不看顺序它们算一种。所以组合的代码要把“已经选过的小编号”排除掉办法是引入参数startIndex下一层递归只能从i 1开始选防止回头。def combine(n, k): res [] path [] def backtrack(start): if len(path) k: res.append(path[:]) return for i in range(start, n 1): path.append(i) backtrack(i 1) # 只能选当前数字后面的数字 path.pop() backtrack(1) return res拿这个例子和46题对照你会发现全排列的循环永远从0开始遍历因为每个位置都可以放任意元素而组合的循环从start开始因为组合不允许回头选择已经排在前面的元素。“从0开始”还是“从start开始”就是排列与组合最核心的分水岭。这一句话基本够了。4.3 回溯题目的常见变体框架回溯算法的题目虽然五花八门但它们的框架高度统一。我总结了一个“变体对照表”供你刷题时参考题目类型代表题关键改动剪枝点全排列无重复46每次从0开始遍历 used数组无全排列有重复47排序 同值剪枝nums[i]nums[i-1]且前一个未用组合无重复77从startIndex开始扫描剩余元素不够k时提前返回组合元素可复用39下一层仍从i开始当前和大于target时跳过子集78每次递归前记录结果无子集去重90排序 同层去重同47题的剪枝逻辑你把这个表记在脑子里刷回溯题的时候先判断这题是排列还是组合元素能不能重复选输入有没有重复元素三个问题一答完代码的主体框架基本就出来了。用这套思路不论LeetCode周赛还是“热门100题”里的回溯题你至少能快速套上模板剩下的就是补剪枝条件。5. 避坑指南实际刷题时最典型的几个错误5.1 错误一结果集append的是同一个引用我前面反复强调path[:]的重要性这里用一个具体现象说明。比如你写res.append(path)最后输出是[[], [], [], [], [], []]。原因是Python的list是可变对象res中存的是path的引用而path在递归结束不断被pop最终变成空列表。你看到的所有“空列表”其实是同一个对象的最终状态。这个坑不只在Python里存在。Java里如果直接res.add(path)结果是类似的需要用new ArrayList(path)创建副本。C里如果你拿的是全局vector也得手动拷贝一份再push进结果集。这是所有语言的通病不单独是Python的锅。5.2 错误二撤销顺序写反或者重复撤销有读者曾经把代码写成used[i] True path.append(nums[i]) backtrack() used[i] False少写了path.pop()。表面看used被正确重置了但path会越积越长最后不会到达终止条件因为len(path)永远大于n或者输出的排列长度全都不对。还有一种情况是撤销顺序颠倒path.pop() used[i] False这两行看似都执行了但放在递归里如果中间有依赖状态判断的逻辑比如剪枝条件读取used[i-1]代码的执行顺序会影响剪枝结果。所以建议养成固定习惯做选择时先修改used再append撤销时先pop再改used顺序保持一致。5.3 错误三在错误的位置初始化path常常有初学回溯的同学把path定义在backtrack函数内部导致每一层递归都有一个新的path结果根本没法累积路径。正确的做法是path和res定义在外部或作为参数传递让递归层与层之间共享同一个列表对象。如果你用Python一个稍微优雅点的做法是把path作为参数传进递归函数def backtrack(path): ... backtrack(path [nums[i]])这种写法的好处是不需要显式pop因为path [nums[i]]生成了新列表原path没变。坏处是每次递归都拷贝一次列表性能略差。对于n 6的小规模输入完全没问题但如果你追求性能还是用全局pathpop的写法。5.4 错误四忽略索引越界在交换法的代码里nums[index], nums[i] nums[i], nums[index]的循环范围是range(index, n)如果写成了range(index 1, n)就会漏掉“当前元素不交换直接固定”的情况导致输出少很多排列。同理在剪枝代码里i 0 and nums[i] nums[i - 1]这行i从0开始时不需要判断因为你没有nums[-1]Python虽然不报错但会取到最后一个元素逻辑就错了。Java和C里nums[-1]会直接越界所以务必加上i 0这个前置条件。5.5 实操调试技巧画递归树 打印状态我刷这题时最常用也最有效的调试方法是“画递归树 打印状态”。代码里临时加一行print(path:, path, used:, used)在backtrack的入口打印能直接看到每一层递归进入时的状态。比如nums [1,2,3]你会在控制台看到path: [] used: [False, False, False] path: [1] used: [True, False, False] path: [1, 2] used: [True, True, False] path: [1, 2, 3] used: [True, True, True] path: [1, 3] used: [True, False, True] ...对照着这棵树你会非常直观地看到什么时候到了叶子节点记录答案什么时候回溯到上一层path变短used复位什么时候遍历完所有分支。等你把状态和递归树对应起来理解回溯就再也不是靠背模板而是真正看懂它在干什么了。6. 从46题走向周赛和热门100题的扩展路径6.1 一道题带出的一类题全排列46题本身不难但它带出的题目链非常长。我在刷LeetCode“热门100题”时发现很多题都是它的亲戚17题 电话号码的字母组合本质是多层“选择列表不同”的回溯。每一层的可选字符都不一样2对应abc3对应def代码里把range(n)换成digits[index]对应的字符串即可。22题 括号生成核心是约束条件剪枝。左括号不超过n右括号不超过左括号数量递归树照样铺开但多了两个if判断。79题 单词搜索矩阵里的回溯。从每个格子出发走四个方向用visited数组记录走过的格子防止重复。这题的“撤销选择”是把格子标记复位。131题 分割回文串回溯选择的是“切分位置”判断子串是否是回文是就递归下一层。这些题的骨架全部逃不出“选择、递归、撤销”六个字。区别在于选择列表怎么定义、结束条件是什么、剪枝条件怎么写。你46题练透了后面的题就是“换皮不换骨”。6.2 周赛里的回溯题怎么快速识别我参加过不少次LeetCode周赛包括搜索里提到的“周赛430”这类场次一个比较实用的经验是当题目输入规模很小比如n 15让你返回所有可能方案、所有组合、所有路径时大概率就是回溯题。为什么因为回溯的时间复杂度是O(n!)或者O(2^n)这种复杂度只能承受非常小的输入。LeetCode官方在题目里给出1 n 6这种小范围输入就是在暗示你用回溯别想什么花哨的优化了。另外周赛里经常把回溯和“状态压缩”结合比如输入是集合或者位运算场景用DFS深度优先搜索在状态空间里枚举。但不管怎么包装n一小于15你脑子里就要立刻拉响回溯的警报。46题作为入门题就是为了让你把这个条件反射建立起来。6.3 回溯和动态规划怎么区分刷题时很多人会纠结这道题该用回溯还是DP我提供一个简单判断方法如果题目要求“返回所有可行解”——用回溯。如果题目要求“返回最优解的数量/最大值/最小值”——用动态规划。举个例子“组合总和IV”377题问的是“有多少种组合”它是DP“组合总和”39题要求“列出所有组合”它是回溯。这个区分的底层原因是回溯遍历了所有解天然知道解长什么样DP只保留状态的最优/数量信息省掉了具体的路径。当然也有混合情况比如“记忆化搜索”本质就是“回溯 缓存”这类题后续刷到再单独研究。46题阶段你先记住上面这个判断标准就足够了。7. 用这套东西解决实际问题的感悟回头看全排列46题之所以被无数人拿来当回溯算法的第一题不是因为它简单而是因为它把所有回溯要素都占全了递归、状态标记、做选择、撤销选择、结果收集。你把它彻底吃透后面的47题、90题、39题、79题全都是一层窗户纸的事。我在实际刷题中还有一个体会回溯题目一定要动手画递归树尤其是前五道题。光看不练以为懂了一到写代码照样卡在“撤销选择”的地方。画树的成本很低但收益非常大。你可以在草稿纸上画也可以像我一样加打印语句在控制台里看。等画到第五题左右回溯的代码基本就是肌肉记忆了。如果你刚刷完这题下一步建议直接做47题“全排列II”因为它的剪枝逻辑和46题只差一行代码是巩固“去重思想”的最佳练习题。做完之后再回头看看这篇文章里的去重代码你会有种“原来就是这回事”的痛快感。