从LeetCode 46全排列看回溯算法本质：递归、DFS与通用模板

1. 这道题为什么值得一啃再啃题目定位与核心考点LeetCode 46“全排列”在面试和算法学习体系里的地位怎么说呢——它是那种“你早晚绕不开绕开了也会回来补课”的题。凡是准备刷题的人大概率会在前五十题、前一百题的热门列表里撞见它凡是在回溯、递归、DFS深度优先搜索这个专题里想要建立手感的人也必然拿它当第一块磨刀石。题面其实很简单给定一个不含重复数字的数组nums返回其所有可能的全排列。示例也很友好nums [1,2,3]输出就有[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]六种。乍看之下这似乎就是个排列组合问题答案总数是n!似乎写个嵌套循环也能凑出来——但问题是n一变大嵌套循环的层数就不可控了你不可能给 8 个数写 8 层循环。这里需要的是一种“不知道要写多少层循环但依然能把所有分支走完”的通用方法这正是回溯算法登场的理由。从考点上看LeetCode 46 主要考察以下几件事一是是否理解**递归是“函数调用自己”而回溯是“递归状态还原”**这两者的关系。很多初学者能写出递归版的子集、组合求和但一到全排列就卡住核心卡点往往是在“如何判断某个元素已经被用过了”这一层。二是是否理解搜索过程本身是一棵多叉树。全排列的搜索树每一层代表“当前位置是排列的第几位”每个节点展开的分支代表“当前位置选哪个剩余的数字”。如果你心里没有这棵树代码就是背下来的稍微改一改参数就可能整个乱掉。三是是否理解时间复杂度为什么是O(n * n!)。很多人知道答案是n!个排列但没意识到生成每个排列的过程中还有一次O(n)的拷贝或拼接操作这直接关系到你在面试里如何向面试官解释复杂度。四是是否具备从一个题迁移到一类题的能力。全排列、组合、子集、括号生成、N 皇后这些题目全部共享同一套回溯模板。把 46 题彻底吃透后面做 47全排列 II、39组合总和、78子集、17电话号码的字母组合时你会发现只是改了“选择列表”的生成逻辑而已。这篇文章就从题目本身出发先把回溯算法的本质讲清楚然后带你从头到尾构建代码再逐行拆解里面每个变量、每个判断条件的含义最后把递归树画出来对照代码走一遍再聊聊去重、复杂度、常见误区这些进阶话题。2. 回溯算法的本质为什么全排列必须用它在开始写代码之前我觉得有必要先花点篇幅讲清楚“回溯”到底是个什么东西。因为如果你只是照着题解抄了一遍swap、dfs过两天再遇到这个题还是会卡壳。真正的核心不是那几行代码而是代码背后的搜索模型。2.1 一个生动的类比一排座位安排面试官想象这样一个场景有 3 个候选人和 3 个面试位每个候选人最终只能坐一个位置每个位置也只能坐一个人你需要列出所有“谁坐哪个位置”的安排方案。最笨的办法是什么暴力枚举先给 1 号候选人选位置有 3 种选择每选完一个再让 2 号候选人在剩余的位置里选有 2 种选择最后 3 号候选人没得选只能坐剩下的 1 个位置。所以总数是3 × 2 × 1 6。这个计算过程看似简单但它背后其实藏着一个关键逻辑每次选位置的“可用选项”随着之前的选择而动态收缩。1 号选了 A 座2 号的选项就从 3 个变成 2 个2 号选了 B 座3 号就只剩 C 座。这个问题之所以不能用固定层数的循环写死是因为“剩余可选项”是动态变化的循环层数取决于n的大小而不是写死在代码里的某个常数。回溯算法恰恰就是来解决这一类“多阶段决策且每个阶段的选项集合随着前面决策变化”的问题。2.2 回溯的“三步走”套路回溯算法的核心可以压缩成三步做选择在当前状态下选择一个可用的选项把局面推进到下一个阶段。递归地进入下一层让下一层决策也重复这个过程直到某个终止条件成立。撤销选择回到当前这一层选择之前的状态尝试下一个选项。听起来是不是很像深度优先遍历没错回溯本质上就是一种带有“撤销”动作的深度优先搜索。它和普通 DFS 最大的区别就在于这个“撤销”动作——你选的这个数只是“暂时占用”一旦以它为前缀的所有排列都已经生成完毕你得把它还回去这样下一个数才有机会被选到同样的位置。举全排列的例子来说当你选[1,2,3]生成完毕如果想生成[1,3,2]就必须在 2 被放到第二位之后把它“撤销”让 3 有机会放到第二位。没有撤销这一步你的搜索就永远卡在第一条分支里走不出来。2.3 全程维护一张“使用清单”在代码层面除了递归深度、路径数组这些常规变量之外全排列题目最关键的额外变量是一个记录“哪些元素已被使用”的布尔数组通常叫做used。used数组的作用是回答一个问题当我要在当前位置填充数字时哪些数字还在“候选名单”里在组合、子集问题中候选数字可以通过“下标递增”天然限制但在排列问题中你随时可能回头去用前面已经跳过的数字所以必须有一个全局可见的标记来记录每个数字的使用状态。这里要特别强调used数组必须是所有递归层级共享的也就是说它不能作为形参在递归调用时拷贝到下一层否则父层修改了状态子层看不到撤销时也无法同步。正确做法是把它放在类的成员变量中或者以引用的方式层层传递。这个细节很多人第一次写的时候会犯迷糊我在后面的代码拆解里会再次强调。2.4 搜索树理解回溯的最好工具如果你把我刚才说的“选择-递归-撤销”过程画出来会得到一棵完整的搜索树。以nums [1,2,3]为例根节点是空排列[]。第一层有三个分支选择 1、选择 2、选择 3分别得到[1]、[2]、[3]。以[1]为例第二层只能在{2,3}里选选择 2 得到[1,2]选择 3 得到[1,3]。第三层只剩最后一个数没有分叉直接得到完整排列。整棵树的叶节点一共有 6 个正好对应 6 种排列。回溯的过程就是在这棵树上做深度优先遍历从根一路走到叶子记录一条路径然后回退到最近的分叉点换一条路再走。“回退”在代码层面就是撤销选择在树的层面就是从当前节点返回父节点。理解了搜索树你就理解了为什么回溯在“方案枚举类”问题中是通用解法因为任何一套完整方案都可以理解为从搜索树的根节点到某个叶节点的一条路径而所有方案的集合就是这棵树所有叶子节点的集合。剩下的事就简单了——你只需要决定两件事每个节点能展开哪些分支选择列表以及走到什么样的节点才算一个完整方案终止条件。3. 从递归树到代码两种主流写法与逐行拆解全排列的实现方式有很多种但主流的就那么两派“交换法”和“used 标记法”。两种方法我都建议大家亲手写一遍因为它们的思维角度不同适用的扩展场景也不一样。3.1 交换法每层固定一个位置先看第一种写法它最直观地映射了搜索树的层级含义。核心思路是递归函数维护一个index表示“当前正在决定排列的第几位”。在index这个位置我们可以把index及其之后任意一个位置的数交换过来作为这一位的结果然后递归处理index1位。def permute(nums): res [] n len(nums) def dfs(index): # 终止条件index 已经移出数组末尾说明所有位置都填好了 if index n: res.append(nums[:]) # 注意一定要拷贝 return for i in range(index, n): # 把第 i 个数交换到 index 位置表示当前位“选中”了它 nums[index], nums[i] nums[i], nums[index] # 递归处理下一位 dfs(index 1) # 撤销交换恢复原状 nums[index], nums[i] nums[i], nums[index] dfs(0) return res我们来拆解每个关键点为什么交换之后要再次交换回来因为下一次循环i进入下一个数时nums 必须保持它原本的顺序。如果换完不换回来数组顺序被打乱后面的交换逻辑就会出各种奇怪的问题。这是整个交换法最容易出错的地方也是“撤销选择”思想的直接体现。为什么res.append(nums[:])而不是res.append(nums)因为nums是同一个对象在递归中被反复修改的。如果直接 append 引用那么最后得到的结果会是同一个列表的 6 份引用而递归结束后这个列表的内容早已面目全非。这个坑我见人踩了无数次面试时也经常拿来考基础。为什么dfs(index 1)之后的撤销语句不能省略如果省略看似也能输出结果但输出可能残缺。比如第一轮走完index0选了 1递归回来后如果不换回 1nums[0]就还是 2此时再把 2 换到index0其实换的是自己和自己的位置3 就没有机会出现在第一位了。换句话说不撤销就会让后续分支被污染。3.2 used 标记法更通用的模板第二种方法更贴近“选择-撤销”的经典模板也是我更推荐大家作为主模板的写法因为它的思路对组合、子集等问题也适用而且不容易在边界情况下犯错。def permute(nums): res [] n len(nums) used [False] * n path [] def dfs(): # 当前排列长度已经等于 nums 长度说明组成了一个完整排列 if len(path) n: res.append(path[:]) return for i in range(n): if not used[i]: # 做选择 used[i] True path.append(nums[i]) # 递归进入下一层 dfs() # 撤销选择 used[i] False path.pop() dfs() return res这段代码的逻辑非常规整。used[i]表示nums[i]是否已经被放进了当前路径每次填一个新位置时遍历整个nums挑一个还没用过的数字递归回退时把标记改回来同时弹出path的末尾元素。这里有个非常关键的理解点path虽然在递归中被反复增删但当前搜索路径的内容其实就保存在path里。也就是说path的长度天然地告诉你“目前搜索到了哪一层”。所以不需要额外的index参数dfs()就能自己知道什么时候该终止。为什么used和path都不作为递归函数的形参如果path以形参path [nums[i]]的形式传给下一层那确实也能工作因为list [x]会创建新列表不会污染父层但这会导致每一层都复制一次数组总时间复杂度的常数项会增大。而且如果used也以拷贝形式传递每一层都要复制整个布尔数组时间开销会更明显。当然如果你的目标是“写起来最不容易出错”那用不可变风格也是合理的但如果目标是“贴近面试最优解”还是建议使用同一个path和used通过修改再撤销来维护状态。从可扩展性来说used 标记法更接近标准回溯模板result [] def backtrack(路径, 选择列表): if 满足结束条件: result.add(路径) return for 选择 in 选择列表: 做选择 backtrack(路径, 新的选择列表) 撤销选择这个模板几乎是 LeetCode 上几十道回溯题的通用骨架。把“选择列表的生成方式”换一换就能解组合、子集、分割回文串、复原 IP 地址等题目。3.3 两种写法的对比与选型建议维度交换法used 标记法空间复杂度O(n)只靠原地交换O(n)pathused是否额外使用标记数组否是撤销操作再次交换改回usedpop理解难度对递归树理解要求较高更贴合通用回溯模板扩展性只适合排列类问题适合排列/组合/子集等一大类典型易错点忘记拷贝结果、交换后未还原忘记恢复used、忘记pop我的建议是平时练习优先使用 used 标记法因为思路统一、模板性强遇到变式时迁移成本最低。但面试时如果时间允许也可以提到“我还会一种交换法”展示你对递归回溯的理解深度。两种都会写比只会一种要稳得多。4. 逐步走查以[1,2,3]为例的递归全过程代码写出来了但只看代码是不够的。我强烈建议你对照递归调用栈把[1,2,3]的完整搜索过程一步一步走一遍。这个过程会解答你很多困惑比如“为什么输出顺序是那样的”“为什么我写的代码会漏掉一些分支”。下面我以 used 标记法为例把整个搜索过程的核心步骤列出来。每个步骤里注意path和used的当前状态。初始状态path[]used[F,F,F]进入dfs()。第 1 层path 空循环i0选 1。path[1]used[T,F,F]递归进入第 2 层。第 2 层path 长度 1循环i0但used[0]为 True跳过i1选 2。path[1,2]used[T,T,F]递归进入第 3 层。第 3 层path 长度 2循环i0、i1都被 used 挡住i2选 3。path[1,2,3]used[T,T,T]递归进入第 4 层。第 4 层len(path)3满足终止条件保存[1,2,3]返回。回到第 3 层撤销对i2的选择used[2]Falsepath.pop()后path[1,2]。循环结束返回到第 2 层。回到第 2 层撤销对i1的选择used[1]Falsepath[1]。循环i2选 3。path[1,3]used[T,F,T]递归进入下一层。第 3 层path[1,3]跳过 used 为 True 的i0和i2i1选 2。path[1,3,2]保存返回。后续过程类似撤销选 2撤销选 3最后回到第 1 层撤销最开始选 1 的操作此时path[]used[F,F,F]然后再让i1选 2 为第一个元素依次排列出[2,1,3]、[2,3,1]等。你可以发现一个规律输出顺序本质上是“字典序式”的深度优先展开。先固定第一位为 1把以 1 开头的所有排列生成完再回到根节点把第一位改为 2。这个顺序不是巧合而是由“从左到右遍历选择列表 深度优先递归”共同决定的。如果你希望输出按字典序严格排序只要保证nums本身有序即可搜索顺序自动满足字典序。在这个走查中有两个时刻特别值得你停下来体会一下“撤销”的必要性。第一个时刻是第 3 层递归返回后。如果没有used[2] False和path.pop()那么path就一直是[1,2,3]used一直是[T,T,T]下一次无论循环到哪个i都进不去if not used[i]分支整个递归就会提前终结。第二个时刻是从整个以 1 开头的分支返回根节点时。如果没有把used[0]恢复为 False那么根节点的循环到i1时仍然会看到used[0]True但这已经不影响i1分支因为 1 本来就不该出现在以 2 开头的排列里第一位已经选了 2。真正会出问题的是当第一位选 1 的分支结束时used[0]还没复位那就会导致后续所有分支都无法再选 1遗漏大量排列。所以撤销必须发生在递归函数 return 之后、紧接着返回上一层时绝不能在res.append之前提前撤销——因为那时候还没生成完毕一撤就全乱了。我在刚开始学回溯时还在res.append(path[:])后面试图加return结果把回溯逻辑彻底搞乱了。其实return加不加都一样因为函数体已经执行到末尾了但如果放在if外面就会导致循环提前终止漏掉大量结果。这类小细节只有亲手走一遍递归栈、逐个打印path才能彻底想明白。5. 进阶避坑哪些坑我踩了至少三遍才彻底弄明白回溯题目的代码往往不长但正因为短一旦出错很难定位。下面这几个坑是我在实际刷题、甚至给别人讲题时反复遇到的每条都可以算得上“新手必踩”级别。5.1 结果拷贝浅拷贝与深拷贝的陷阱第一个坑就是之前提到的res.append(nums[:])和res.append(path[:])。无论是交换法还是 used 标记法nums和path都是同一个对象在递归中被反复修改的。如果写成res.append(nums)或res.append(path)那么保存的只是引用而不是快照。为什么会这样呢因为 Python 的列表变量是引用类型append一个列表并不会复制它的内容而只是把对象的引用放入res。递归结束后这个列表对象被改得面目全非于是你的res里存的就是一堆完全相同的“最后状态”。解决办法就是用切片[:]或list()创建一份浅拷贝。这里有个值得注意的细节因为路径元素是整数这样不可变对象浅拷贝已经足够不需要深拷贝但如果路径里存的是嵌套列表你就得考虑深拷贝了。5.2 撤销不及时漏掉pop或者漏掉used标记会导致结果成倍损失第二个坑是撤销写不完整。used 标记法里“一对操作”必须成对出现做选择时used[i]Truepath.append(nums[i])撤销时used[i]Falsepath.pop()。少一个都不行。如果漏掉poppath会无限膨胀最终结果里的每个排列长度可能都不对。如果漏掉used复位后续分支会跳过一些本不该跳过的数字。我曾经写错过一次把path.pop()写在了used[i]False的前面但其实顺序无所谓——只要两个语句都执行到。真正关键的是它们必须在同一个递归层级的同一个函数调用里、且发生在递归调用之后。如果你把撤销语句写到了if分支外面或者因为某个continue导致跳过了撤销语句问题就会出现。5.3 终止条件的判定位置别在“不该停止的时候”停止第三个坑是终止条件的放置位置。正确做法是进入dfs()时先判断len(path) n一旦成立就保存结果并return。这个return意味着“不再需要展开任何分支了”因为已经满员了。但如果把终止条件放到 for 循环内部去判断可能就会出现子排列被提前保存的问题。比如在if not used[i]之后先判断len(path) 1 n再保存虽然看起来“只差一步”但逻辑会复杂很多而且你需要在每个选择之后都维护一次判断非常容易漏。统一入口判断是更稳的做法。5.4 输入含有重复数字LeetCode 47 的天然延伸原题明确说了输入不含重复数字但面试官经常立刻追加一问如果nums里有重复数字怎么做这就是 LeetCode 47“全排列 II”。核心思路是在 used 标记法基础上加一个排序 剪枝操作。排序的目的是让相同数字都相邻然后加一个判断if i 0 and nums[i] nums[i-1] and not used[i-1]: continue这行剪枝的逻辑是对于相同的数字只有前一个相同数字已经被使用过当前这个才能被使用从而保证相同数字的相对顺序固定避免生成重复排列。或者说如果前一个相同数字还没用过说明当前分支会产出和前一个数字开头的排列完全相同的路径直接跳过即可。这个剪枝条件里的not used[i-1]是很多题解里最容易引起困惑的部分认真想清楚了它你对回溯的理解又能拔高一层。5.5 时间复杂度的正确表述最后说一说复杂度。很多初学者会说全排列复杂度是O(n!)但如果面试官问得细一点这个答案是不够准确的。因为生成每个排列时把path拷贝进结果列表需要O(n)的时间搜索树总共生成的排列数就是n!个。所以总时间复杂度应是O(n * n!)。空间复杂度方面used 标记法需要O(n)的path、O(n)的used、以及递归调用栈深度O(n)加起来是O(n)。但结果列表本身不算在内——如果要算上结果存储那自然是O(n * n!)不过大多数题目讨论时空复杂度时不把输出结果计入因为无论什么算法都必须返回这么多数据。6. 从全排列到一类题回溯模板的迁移实战能把 46 题独立做出来只是第一步真正的价值在于把这道题内化成“一套武器”能迁移到其他题型上。6.1 全排列 IILeetCode 47刚才已经提到了核心思路排序 去重剪枝。这里直接把完整代码贴出来方便对比def permuteUnique(nums): res [] nums.sort() n len(nums) used [False] * n path [] 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与 46 题相比只有两处变化排序以及那行重复剪枝。这就是标准回溯模板的威力——你改动的是“选择列表的过滤条件”而不是整个框架。6.2 组合总和LeetCode 39选择列表从“未使用的数”变成了“大于等于当前位置的数”组合问题和排列问题最大的区别是组合不关心内部顺序[1,2]和[2,1]视为同一个方案。所以搜索时不能回头选前面的数。做法是在递归函数里维护一个start下标每次从start开始选。def combinationSum(candidates, target): res [] path [] def dfs(start, remaining): if remaining 0: res.append(path[:]) return if remaining 0: return for i in range(start, len(candidates)): path.append(candidates[i]) dfs(i, remaining - candidates[i]) # 注意还是从 i 开始因为可重复使用 path.pop() dfs(0, target) return res看核心三段式“做选择—递归—撤销”完全没有变变的只是 for 循环的起点变成了start以及递归参数从“层数”变成了“剩余目标和”。6.3 子集问题LeetCode 78不需要严格固定长度的组合子集问题里任何一个选择列表的子序列都是一个合法结果所以“终止条件”不再依赖固定的len而是每当进入递归都可以保存当前pathdef subsets(nums): res [] path [] def dfs(start): res.append(path[:]) for i in range(start, len(nums)): path.append(nums[i]) dfs(i 1) path.pop() dfs(0) return res这个问题的终止条件藏在哪里藏在了for循环自然结束的时候。当start越界时循环体不会执行递归自然返回所有子集都已经收集完毕。把这三个题放在一起对比你就能看到回溯的“常量”和“变量”常量做选择、递归、撤销的主体框架需要维护的path需要拷贝进结果列表。变量选择列表的范围排列是[0..n)组合和子集是[start..n)终止条件的判断方式长度达到固定值 / 剩余值归零 / 无所谓去重的预处理。6.4 其他常见变式括号生成、N 皇后、复原 IP 地址括号生成可以看作“选择列表只有左括号和右括号的排列问题”需要额外维护左括号和右括号的剩余计数N 皇后则是“每一行选一个列位置”的排列问题只不过合法性检查变成了对角线冲突复原 IP 地址则是“在一个字符串里选三个分割点”的组合问题。它们全都能套回同一个模板框架里。这也解释了一个现象为什么正规的算法课程和面试准备都特别强调“刷熟回溯”。因为回溯是连接暴力枚举和系统性搜索之间的一座重要桥梁一旦把握住模板几十道看似花样百出的题目在你眼里不过是排列、组合、子集三种基本形态的变形组合。7. 我建议的刷题节奏与自查清单结合我自己刷 LeetCode 的经验如果你是想稳步掌握这一类题目建议按照下面这个节奏走。第一步用 46 题建立手感。先别急着看题解自己尝试写。写不出来也没关系看一遍题解后合上电脑从零开始写出完整可运行的代码。这一步会让你意识到“看懂了”和“写得出来”之间存在一条巨大的鸿沟。第二步走查递归过程。我强烈推荐你在代码里加几个print(path)或者调试断点把[1,2,3]的完整搜索过程打印出来对着递归树核对一遍。这一步做完“回溯”这个概念就不再是抽象的了。第三步按模板做变式题。做完 46立刻做 47、78、39、40、17。你会发现做题速度会有明显提升。如果时间有限优先做 47 和 78因为一个是去重一个是组合思路的延伸。第四步给自己准备一个“自查清单”。每次写完回溯题问自己四个问题终止条件写对了吗结果拷贝了吗每一步的撤销完整吗选择列表有没有被正确过滤这四个问题能拦住 90% 的 bug。我在带人刷题时还发现一个规律很多人在能写出代码之后又会栽在“口述思路”上。面试时除了要跑通代码还需要清晰解释为什么这个算法不会漏解、不会重复。所以我建议你平时做题时用三句话把思路讲给自己听我搜索的是什么样的决策树每个节点的分支是怎么定义的到达什么条件时算一个完整解。这三句话能讲明白面试时你的回溯环节基本就是加分项了。最后再分享一个小技巧如果你在刷题时经常遇到递归栈过深、无法直观调试的题目可以先把n设成 3 或 4把nums设成最简单的连续整数逐层打印path和used的状态。很多回溯里复杂的剪枝条件在n4的小数据下会变得非常直观定位 bug 的速度能快出一大截。