看到“46.全排列”这个标题刷题的人应该都不陌生。这是一道几乎被所有回溯算法教程当作开篇的题目给定一个不含重复数字的数组返回所有可能的全排列。题目描述只有一句话函数签名也简单得不能再简单可就是这道题在初学阶段卡住过不少人。我第一次写的时候也绕了很大弯子对着递归函数里那一次swap反复想了好久才真正明白什么叫“状态恢复”。这篇文章就把这道题彻底拆开——从为什么需要回溯到三种实现写法的取舍再到调试过程中最容易踩的坑最后把全排列的模板迁移到组合、子集和N皇后这类题型上。不管你是刚接触算法的初学者还是准备面试想快速回顾回溯框架的开发者都能从中拿到可以直接用的东西。1. 为什么“全排列”是回溯算法的敲门砖1.1 题面很短数学结构却很陡全排列的数学背景并不复杂。给定n个互不相同的元素它们的所有排列方式一共有n!种。比如三个数[1,2,3]排列就是1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1一共6种正好是3的阶乘。这个数字会随着n的增长变得非常夸张5的阶乘是1208的阶乘是4032010的阶乘是3628800。也就是说哪怕输入只有10个数结果集里也有几百万个排列每个排列还要作为一个独立数组保存。这个“输出本身就可能很大”的属性决定了这道题的解法必须围绕“如何高效地枚举所有情况”展开。我在实际刷题时发现很多人对全排列的困惑不是“不知道要枚举”而是“不知道怎么写循环才能把所有情况不漏不重地列出来”。两数排列可以写两层for三数排列写三层for那四数、五数呢代码长度会跟着n线性膨胀这显然不是通用解法。回溯算法正是为了解决这类“循环层数不确定”的枚举问题而存在的。1.2 循环嵌套的暴力思路为什么撑不住先看一个最直观的暴力想法既然排列就是每个位置选一个不同的数那就对第一个位置枚举n种可能对第二个位置枚举n-1种可能依次类推。如果能够根据n动态生成这么多层循环理论上也能跑出答案。但问题是普通编程语言里for循环的嵌套层数是写代码时就已经固定的不可能在运行时凭空生成。有人会想到用递归代替动态循环层数。递归的深度本身就是可变的每一层相当于一层for。这个思路方向是对的但紧接着就会出现新问题第二层循环怎么知道第一层选了哪个数怎么保证后面的选择不再重复两个分支之间如何避免互相污染这些问题如果不在数据结构上做好设计写出来的递归很快会陷入“无限递归”或者“输出大量重复排列”的泥潭。回溯算法的价值正在于此。它把“当前已经选了哪些数”作为一种状态在递归中显式传递每层只从剩余的未选元素中做选择一旦这条路走到底就返回上一层退回上一步的选择继续尝试其他可能。这样既不需要知道循环总层数又能天然保证不重不漏。这也是全排列作为回溯入门题的重要原因之一——它把这个框架最核心的机制体现得淋漓尽致。1.3 这道题为什么适合作为回溯入口我个人觉得全排列作为回溯开篇题有四个很实际的理由。第一它的选择规则足够简单。候选集就是“还没用过的数字”不需要像组合问题那样额外维护起始下标。第二它的结束条件非常清晰——路径长度等于数组长度。第三它天然要求“状态恢复”如果不恢复结果就会错得一塌糊涂这让初学者能立刻体会到回溯和普通递归的关键区别。第四它向后延伸能力很强稍微改一改限制条件就能变成重复元素排列、组合、子集、N皇后等一系列高频题。换句话说吃透全排列这一道题等于把回溯算法的通用骨架打了一遍底。之后再遇到同类题只需要记住“结束条件怎么定、选择列表怎么缩、状态怎么恢复”就能很快写出答案。2. 回溯的决策树视角路径、选择列表与结束条件2.1 把排列过程画成一棵隐式树回溯算法的核心可以理解为一棵“隐式决策树”。以[1,2,3]为例第一次选择可以把1、2、3三个数中的任意一个放到排列第一个位置于是分出三个大分支。在选了1的分支里第二个位置只能从[2,3]里选再分出两个分支。到第三个位置时剩下的唯一数字自动填入分支到这里终止。整棵树从根节点到每个叶子节点都对应一个完整的排列。路径上的每一层选择就是排列中对应位置上的数字。树的深度等于数组长度n每一层的分支数逐层递减第一层n种第二层n-1种第三层n-2种最后一层1种。所以叶子节点总数正好就是n乘以n-1乘以…乘以1也就是n!。这样一看回溯的本质就是深度优先遍历一棵动态生成的树。注意“动态生成”这个词我们并不是事先把整棵树建好再去遍历而是在遍历的同时通过递归和循环不断展开新的分支。这样做的好处是树有多大我们就只展开到多大不会浪费额外的树的存储空间。2.2 三个关键变量的工程含义市面上的回溯模板千篇一律但真正重要的是理解模板里那三个变量到底在干什么。第一个是“路径”也就是当前已经做出的选择序列。在全排列里它代表正在构造的排列前缀。第二个是“选择列表”也就是当前状态下还能选哪些数。在无重复元素的全排列里它就是“所有还没被用过”的数字。第三个是“结束条件”也就是什么时候可以把当前路径作为答案记录下来。这三个变量映射到代码上一般是这样的形态def backtrack(路径, 选择列表): if 满足结束条件: 记录结果 return for 选择 in 选择列表: 做选择 backtrack(新路径, 新选择列表) 撤销选择先不要急着背把这个框架看成一种思维方式每到一层就问自己三个问题——这条路走到了没有这层有哪些选择可以做做完这次选择后下一层还剩下哪些选择把这三个问题回答清楚代码自然就能写出来。2.3 递归返回后的状态恢复一次也不能少回溯和普通递归最大的不同就是“撤销选择”这一步。普通递归在进入子问题时会带着子问题的计算结果返回上层无需还原任何东西回溯则不然因为同一层的多个分支会复用同一份状态数据如果不把这一步的状态恢复到进入递归之前的样子下一个分支就会把上一个分支留下的残留状态误认为是自己的选择。举一个实际场景在标记法实现里进入递归前会把used[i]设为True同时把数字加入路径递归返回后必须立刻把used[i]改回False并把路径末尾的数字弹出。漏掉其中任何一个要么导致某些分支以为某个数字还在使用中而跳过要么导致路径里残留着不属于当前分支的数字。我在帮人排查代码时发现最典型的错误就是只改了used数组却忘了path.pop结果所有结果都变成了同一根路径不断加长的快照。理解状态恢复还有一个更形象的角度把这棵树想成迷宫回溯就是“退回到岔路口再走另一条路”。如果不记得把走过的脚印擦掉后面的人也就是其他分支就会以为前面那条路已经被占了从而漏掉大量正确答案。3. 三种代码实现路线交换、used标记与迭代生成3.1 路线一交换法原地修改nums数组交换法是很多教材喜欢用的实现方式核心思路是不额外维护一个路径数组而是直接在当前nums上做两次swap把某个数换到当前起始位置递归完成后换回去。def permute(nums): res [] def dfs(start): # 所有位置都已经固定记录当前排列 if start len(nums): res.append(nums[:]) return # 当前位置可以从 start..n-1 中选一个数 for i in range(start, len(nums)): # 选择把 nums[i] 换到 start 位置 nums[start], nums[i] nums[i], nums[start] # 进入下一层固定下一个位置 dfs(start 1) # 撤销选择换回来 nums[start], nums[i] nums[i], nums[start] dfs(0) return res这个写法的优势非常明显不需要额外的path数组也不需要used数组空间开销更小。它天然利用nums本身来记录排列状态。但代价是理解成本更高因为递归过程中nums数组的内容一直在变调试时如果打印每个分支的状态很容易被“为什么start位置不是原来的数了”搞晕。另一个特点是交换法生成的排列顺序并不是字典序。如果题目要求按字典序输出全部排列交换法需要配合排序或者在输出后统一排序否则可能不满足题意。同时也注意res.append(nums[:])必须拷贝直接append(nums)会让结果集里所有元素共用同一个列表对象。3.2 路线二used数组标记法逻辑最直白如果追求“一眼能看懂”我强烈推荐标记法。它用path数组记录当前路径上的数字用used数组标记哪些数字已经被用过递归时遍历整个nums跳过所有已使用的元素。def permute(nums): res [] path [] used [False] * len(nums) def dfs(): 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]) # 进入下一层 dfs() # 撤销选择 path.pop() used[i] False dfs() return res标记法的优点是选择列表非常明确“所有used[i]为False的数”。每次递归只需要看used数组不需要关心nums数组有没有被打乱。路径顺序和最终输出顺序也符合直觉——你按什么顺序遍历nums排列就会按什么顺序生成。它的缺点是多了两个额外空间path和used。在n很大时这个空间开销和结果数量相比其实微不足道所以绝大多数场景下标记法是更推荐的选择。我自己刷题和写教程时默认都用这个版本只有在面试官明确要求“原地完成”时才会切到交换法。3.3 路线三迭代生成与字典序思路除了递归回溯还有一种不讲递归的生成方式按字典序一步一步求出下一个排列。这个方法在“下一个排列”这道题里是主角当作全排列的完整解法也完全可以。思路是先对数组排序然后反复调用“找下一个排列”的过程直到不存在下一个排列为止。找下一个排列的经典步骤是从右往左找到第一个升序对(nums[i] nums[i1])然后从右往左找到第一个大于nums[i]的数nums[j]交换i和j位置最后把i1到末尾的部分反转。这个过程可以通过一个while循环反复执行不断产出新排列。在工程实践中Python自带的itertools.permutations已经封装好了全排列生成日常写业务代码时完全可以直接用。但在算法面试或刷题场景下我建议还是手写回溯。因为面试官考察的不是“你会不会调库”而是“你懂不懂递归和状态管理”。用库函数一步出结果反而没法展示解题思路。3.4 三种实现对比与选型建议用一张表把三者的关键差异列出来方便大家在面对不同题目时快速做选择。实现方式额外空间输出顺序理解成本适用场景交换法低原地修改非字典序偏高面试官要求原地、空间敏感used标记法path used按遍历顺序低通用场景最推荐迭代生成无递归栈字典序中需要字典序输出、或求下一个排列实际选型时我的经验是默认标记法因为可读性最好如果题目要求空间O(1)就换交换法如果要用字典序且不允许递归深度过大就上迭代法。三种写法都值得手写一遍写多了自然就明白各自的边界在哪里。4. 实际调试中的四个高频坑与完整排查链路4.1 坑一结果集里全是同一个列表这是一个非常经典的“新手段错误”。现象是输出的res长度正确但里面的每个排列内容一模一样全是最后一种排列。我第一次遇到这个问题时排查链路是这样的先在递归结束处加了一行print发现每次要append的path内容确实是不同的。那为什么res里的最终结果一样问题就出在res.append(path)而不是res.append(path[:])上。Python里列表是引用类型path变量指向的是同一个列表对象。回溯过程中path会不断被修改虽然每次append时path的内容是对的但这个对象在后续回溯中会被pop和append改变。由于所有res元素都是同一个对象的引用当整个递归运行结束path指向的那个列表已经变成了最后一种排列于是res里所有元素看起来都一模一样。修复很简单append(path[:])拷贝一份当前快照。这个坑在C里对应vector push_back(path)和push_back(path的拷贝)的区别在Java里对应add(new ArrayList(path))。凡是记录结果必须考虑是记录引用还是记录值。4.2 坑二used状态没有还原导致分支缺失现象输出结果数量不对通常比n!少。比如[1,2,3]只输出了两三种排列而且其中还夹杂着长度不到3的“半截排列”。排查时我发现了这样的代码used[i] True path.append(nums[i]) dfs() # path.pop() 忘了写 # used[i] False 忘了写如果只执行了used[i] True而没有在递归返回后恢复那么第一个分支走完后used里的标记全部为True后面的循环执行到任何i都会跳过整个递归树只展开了一束路径。如果path.pop忘了写路径只会越加越长递归结束条件永远无法触发最终要么栈溢出要么输出一堆不完整的组合。这类问题的排查链路很有规律先看结果数量再打印每个分支进入和退出时的path与used状态通常一眼就能看出“进入时选了什么退出时有没有还回去”。修复也很机械在递归调用返回后务必成对执行撤销操作。可以把“做选择”和“撤销选择”两行代码写在一起形成条件反射般的代码习惯。4.3 坑三交换法里swap的时机与下标越界交换法代码短但陷阱也不少。我自己调试时踩过的一个典型错误是在dfs(start)的for循环里写成dfs(i 1)而不是dfs(start 1)。为什么必须传start 1因为交换法基于一个前提区间[0, start-1]已经被前面的层固定好了当前层只需要决定位置start放哪个数。for循环枚举的是“把nums[i]换到start位置”换完以后我们应该去固定下一个位置也就是start 1。如果写成dfs(i 1)当i不是start时就会出现跳过中间位置的问题导致生成的排列长度错误或直接越界。还有一种情况是swap次数混乱。有的新手会在递归返回后忘记swap回来这样下一轮循环基于的是被上一轮修改过的数组产生的排列大量重复且错乱。排查手段是打印每次swap前后的数组内容确认“进入递归前换出去返回后换回来”是否严格成对。只要把交换法理解成“当前层和它管理的for循环共同负责位置start”下标问题就不容易再犯。4.4 坑四输入长度稍大就超时或内存暴涨严格来说这不是代码逻辑问题而是对输出规模没有预判。前面算过10个元素有3628800种排列每个排列如果作为独立数组保存内存占用轻轻松松上几百MB。很多在线评判平台的单个用例往往把n限制在8或者10左右就是为了让答案能完整保存下来。当你把n设为11、12去测时超时或者内存溢出都是正常现象不是算法写错了。遇到这种问题排查第一步不是优化代码而是检查题目约束。如果是自己做测试建议n不要超过10否则再优秀的回溯代码也会因为输出数量过大而卡死。如果题目本身允许n很大但要求返回结果那唯一的出路可能是改变返回策略比如改为生成器逐条产生排列或者只返回排列总数。这个坑提醒我们写代码之前先评估答案规模是一种非常实用的工程习惯。5. 一套回溯模板迁移组合、子集与N皇后5.1 抽象出通用回溯模板全排列的框架稍微抽象一下就能覆盖一大批高频回溯题。在我看来所有回溯题目都可以从三个维度去套模板结束条件怎么定义选择列表怎么生成状态怎么撤销。def backtrack(路径, 参数): if 结束条件: 记录结果 return for 选择 in 可选择的列表: 做选择 backtrack(更新后的路径, 新参数) 撤销选择接下来的重点就是看如何改这三处。组合题改的是选择列表的生成方式子集题改的是记录结果的时机包含重复元素的排列题改的是剪枝条件N皇后题改的是路径的数据结构和合法性检查。5.2 组合用startIndex压缩选择范围组合题通常要求从n个数中选出k个不考虑顺序。比如“从[1,2,3]里选2个数”结果是[1,2]、[1,3]、[2,3]而不是所有排列。它和全排列最大的区别是同一组数字不能因为顺序不同而重复出现。因此选择列表不能再是“所有没用过的数”而是“从某个下标开始的所有数”。做法是在dfs参数里加一个startIndex每层循环从startIndex开始并且递归传入i 1表示下一层只能选择更靠后的元素。def combine(n, k): res [] path [] def dfs(start): if len(path) k: res.append(path[:]) return for i in range(start, n 1): path.append(i) dfs(i 1) path.pop() dfs(1) return res这个startIndex其实就是组合题的核心它代替了used数组的部分功能只要保证后面选的数下标永远比前面大就不会产生重复组合。理解这一点组合题就只剩一个剪枝优化当剩余元素数量不够填满路径时提前返回。5.3 子集在递归过程中记录所有节点子集题和全排列、组合都不一样它要求输出所有元素的全部子集包括空集和全集。在决策树视角里全排列是只记录叶子节点组合是记录深度恰好为k的节点而子集是记录整棵树上的每一个节点。def 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这个写法非常简洁res.append放在递归函数开头而不是等到结束条件。这样空集、单元素子集、多元素子集都会被依次记录下来。很多人在理解子集时会卡一下“为什么这样就能不重不漏”其实和组合题的逻辑一模一样startIndex保证子集内元素的下标严格递增因此不会出现[1,2]和[2,1]这种重复表示。5.4 排列进阶重复元素去重怎么剪把全排列加上“数组可能包含重复数字”这个条件就变成了一道经典变体题。比如输入[1,1,2]正确输出只有3种排列[1,1,2]、[1,2,1]、[2,1,1]而错误的排列版本可能会输出6种其中包含大量重复。处理思路是先把数组排序让相同数字相邻然后在回溯的for循环里加一个剪枝条件。剪枝的核心判断是如果当前元素和前一个元素相同并且前一个元素在本层还没有被用过就跳过当前分支。nums.sort() used [False] * len(nums) 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]) dfs() path.pop() used[i] False这里有个容易混淆的点为什么条件是not used[i - 1]而不是used[i - 1]因为我希望同一层中相同数字只从最左边的那个开始尝试。如果前一个相同数字已经用过且被撤销说明它已经作为当前层的一个分支完整搜索过当前这个相同数字就不必再重复走一遍。如果前一个相同数字还在used状态说明我们在更深的层级中此时应该允许继续使用否则会漏掉像[1,1,2]里第二个1出现在排列第二位的情况。5.5 N皇后二维棋盘的状态校验N皇后问题看起来和排列毫无关系但它依然是同一套回溯模板。棋盘上的每一行相当于排列中的每一层每个皇后所在的列相当于这一层选中的数字。区别只在于合法性判断从“是否用过”变成了“和之前所有皇后是否冲突”。经典的优化做法是用三个数组分别标记列、主对角线、副对角线的占用状态。某个位置(row, col)如果被占用它所在的主对角线特征值是row - col副对角线特征值是row col这两个值在整张棋盘上都能唯一标识一条对角线。递归时逐行放皇后每次选择一列判断列和对角线是否冲突不冲突就占用并进入下一行回溯时再释放。def solve_n_queens(n): res [] board [[.] * n for _ in range(n)] col_used [False] * n diag1 [False] * (2 * n) diag2 [False] * (2 * n) def dfs(row): if row n: res.append([.join(r) for r in board]) return for col in range(n): d1 row - col n d2 row col if col_used[col] or diag1[d1] or diag2[d2]: continue col_used[col] diag1[d1] diag2[d2] True board[row][col] Q dfs(row 1) board[row][col] . col_used[col] diag1[d1] diag2[d2] False dfs(0) return res可以看到N皇后只比全排列多了一个“合法性判断”的环节。路径从一维列表变成了二维棋盘但“做选择、递归、撤销选择”的主干完全没变。这正好印证了前面那句话全排列模板吃透了迁移到其他回溯题只是改参数的问题。6. 从刷题到面试把全排列讲出层次感6.1 面试中的标准破题顺序如果面试中遇到全排列我的建议是不要在拿到题目后立刻写代码。可以先花几十秒把思路讲清楚顺序大概是先确认输入约束比如是否有重复元素、是否需要按字典序输出然后说“全排列本质是一棵决策树每个位置选择未被使用的数字直到所有数字都被选完”再说“我准备用回溯实现用一个path记录当前排列用一个used数组标记已使用数字递归结束时拷贝快照”最后分析复杂度。这个顺序看起来很简单但很多人在面试时因为太紧张直接把模板往白板上一默写结果面试官追问“你的used数组为什么在这里恢复”就答不上来。按先思路、再实现、后验证的顺序来反而显得思路清晰。哪怕代码有一两个小瑕疵面试官也会更愿意引导你修正。6.2 复杂度为什么是O(n * n!)全排列的时间复杂度有两个部分要算清楚。第一部分是递归树上一共会产生多少个节点。叶子节点有n!个从根到叶子的路径长度是n所以整棵树节点数量大致是n乘以n!的量级。第二部分是每到达一个叶子节点为了保存结果需要拷贝长度为n的路径数组这部分也是O(n)。因此总时间复杂度是O(n * n!)。空间复杂度要从三部分看递归栈深度是npath数组长度是nused数组长度是n结果集占用的空间不计入算法本身的额外空间。所以额外空间复杂度是O(n)结果集空间则是O(n * n!)这是由输出规模决定的。如果面试问“能不能优化”通常回答是结果集必然占用这么多空间代码使用的辅助空间已经可以做到O(n)没有更优的排列生成方式能把结果数量变少。6.3 常见延伸问题全排列的变体很多面试官经常会在此基础上追问。第一个是“下一个排列”它不再要求输出全部只要求按字典序求出某个排列的下一个排列解法就是我前面介绍的迭代思路。第二个是“带重复元素的全排列”核心就是排序加used[i-1]判断的剪枝。第三个是“排列中的第k个”可以结合阶乘数系统来做进一步考察对阶乘结构的理解。第四个是“字符串全排列”本质和数组全排列完全一样只是把数字换成字符。我在准备面试时通常会把这几道题连着刷一遍。因为它们共享同一套决策树思想区别只是在于枚举规则和剪枝条件。把这些变体都理清楚后再遇到类似题基本不会慌。6.4 我的个人经验最后分享一个我自己的习惯每次讲全排列时我都会先在纸上画一个三层的小决策树把[1,2,3]的分支画出来然后指着树说“递归就是深度优先遍历这棵树回溯就是回到父节点重新走另一条分支”。这个图一画出来面试官基本就明白我已经掌握了回溯的本质后续追问的难度会明显降低。还有一个小技巧写代码时我会刻意把“做选择”和“撤销选择”两行代码放在同一缩进层次紧挨着写中间只隔一行递归调用。这样在review时能一目了然地检查状态是否成对出现。很多新手漏掉path.pop就是因为在代码里把它们隔得太远视觉上根本没形成“对称”的暗示。这个习惯帮我避开了不少低级错误也推荐给大家。 
长河君 · 2026/10/16 13:33:10 · 阅读 1.2k 回溯算法入门指南：全排列的三种实现与状态恢复详解
看到“46.全排列”这个标题刷题的人应该都不陌生。这是一道几乎被所有回溯算法教程当作开篇的题目给定一个不含重复数字的数组返回所有可能的全排列。题目描述只有一句话函数签名也简单得不能再简单可就是这道题在初学阶段卡住过不少人。我第一次写的时候也绕了很大弯子对着递归函数里那一次swap反复想了好久才真正明白什么叫“状态恢复”。这篇文章就把这道题彻底拆开——从为什么需要回溯到三种实现写法的取舍再到调试过程中最容易踩的坑最后把全排列的模板迁移到组合、子集和N皇后这类题型上。不管你是刚接触算法的初学者还是准备面试想快速回顾回溯框架的开发者都能从中拿到可以直接用的东西。1. 为什么“全排列”是回溯算法的敲门砖1.1 题面很短数学结构却很陡全排列的数学背景并不复杂。给定n个互不相同的元素它们的所有排列方式一共有n!种。比如三个数[1,2,3]排列就是1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1一共6种正好是3的阶乘。这个数字会随着n的增长变得非常夸张5的阶乘是1208的阶乘是4032010的阶乘是3628800。也就是说哪怕输入只有10个数结果集里也有几百万个排列每个排列还要作为一个独立数组保存。这个“输出本身就可能很大”的属性决定了这道题的解法必须围绕“如何高效地枚举所有情况”展开。我在实际刷题时发现很多人对全排列的困惑不是“不知道要枚举”而是“不知道怎么写循环才能把所有情况不漏不重地列出来”。两数排列可以写两层for三数排列写三层for那四数、五数呢代码长度会跟着n线性膨胀这显然不是通用解法。回溯算法正是为了解决这类“循环层数不确定”的枚举问题而存在的。1.2 循环嵌套的暴力思路为什么撑不住先看一个最直观的暴力想法既然排列就是每个位置选一个不同的数那就对第一个位置枚举n种可能对第二个位置枚举n-1种可能依次类推。如果能够根据n动态生成这么多层循环理论上也能跑出答案。但问题是普通编程语言里for循环的嵌套层数是写代码时就已经固定的不可能在运行时凭空生成。有人会想到用递归代替动态循环层数。递归的深度本身就是可变的每一层相当于一层for。这个思路方向是对的但紧接着就会出现新问题第二层循环怎么知道第一层选了哪个数怎么保证后面的选择不再重复两个分支之间如何避免互相污染这些问题如果不在数据结构上做好设计写出来的递归很快会陷入“无限递归”或者“输出大量重复排列”的泥潭。回溯算法的价值正在于此。它把“当前已经选了哪些数”作为一种状态在递归中显式传递每层只从剩余的未选元素中做选择一旦这条路走到底就返回上一层退回上一步的选择继续尝试其他可能。这样既不需要知道循环总层数又能天然保证不重不漏。这也是全排列作为回溯入门题的重要原因之一——它把这个框架最核心的机制体现得淋漓尽致。1.3 这道题为什么适合作为回溯入口我个人觉得全排列作为回溯开篇题有四个很实际的理由。第一它的选择规则足够简单。候选集就是“还没用过的数字”不需要像组合问题那样额外维护起始下标。第二它的结束条件非常清晰——路径长度等于数组长度。第三它天然要求“状态恢复”如果不恢复结果就会错得一塌糊涂这让初学者能立刻体会到回溯和普通递归的关键区别。第四它向后延伸能力很强稍微改一改限制条件就能变成重复元素排列、组合、子集、N皇后等一系列高频题。换句话说吃透全排列这一道题等于把回溯算法的通用骨架打了一遍底。之后再遇到同类题只需要记住“结束条件怎么定、选择列表怎么缩、状态怎么恢复”就能很快写出答案。2. 回溯的决策树视角路径、选择列表与结束条件2.1 把排列过程画成一棵隐式树回溯算法的核心可以理解为一棵“隐式决策树”。以[1,2,3]为例第一次选择可以把1、2、3三个数中的任意一个放到排列第一个位置于是分出三个大分支。在选了1的分支里第二个位置只能从[2,3]里选再分出两个分支。到第三个位置时剩下的唯一数字自动填入分支到这里终止。整棵树从根节点到每个叶子节点都对应一个完整的排列。路径上的每一层选择就是排列中对应位置上的数字。树的深度等于数组长度n每一层的分支数逐层递减第一层n种第二层n-1种第三层n-2种最后一层1种。所以叶子节点总数正好就是n乘以n-1乘以…乘以1也就是n!。这样一看回溯的本质就是深度优先遍历一棵动态生成的树。注意“动态生成”这个词我们并不是事先把整棵树建好再去遍历而是在遍历的同时通过递归和循环不断展开新的分支。这样做的好处是树有多大我们就只展开到多大不会浪费额外的树的存储空间。2.2 三个关键变量的工程含义市面上的回溯模板千篇一律但真正重要的是理解模板里那三个变量到底在干什么。第一个是“路径”也就是当前已经做出的选择序列。在全排列里它代表正在构造的排列前缀。第二个是“选择列表”也就是当前状态下还能选哪些数。在无重复元素的全排列里它就是“所有还没被用过”的数字。第三个是“结束条件”也就是什么时候可以把当前路径作为答案记录下来。这三个变量映射到代码上一般是这样的形态def backtrack(路径, 选择列表): if 满足结束条件: 记录结果 return for 选择 in 选择列表: 做选择 backtrack(新路径, 新选择列表) 撤销选择先不要急着背把这个框架看成一种思维方式每到一层就问自己三个问题——这条路走到了没有这层有哪些选择可以做做完这次选择后下一层还剩下哪些选择把这三个问题回答清楚代码自然就能写出来。2.3 递归返回后的状态恢复一次也不能少回溯和普通递归最大的不同就是“撤销选择”这一步。普通递归在进入子问题时会带着子问题的计算结果返回上层无需还原任何东西回溯则不然因为同一层的多个分支会复用同一份状态数据如果不把这一步的状态恢复到进入递归之前的样子下一个分支就会把上一个分支留下的残留状态误认为是自己的选择。举一个实际场景在标记法实现里进入递归前会把used[i]设为True同时把数字加入路径递归返回后必须立刻把used[i]改回False并把路径末尾的数字弹出。漏掉其中任何一个要么导致某些分支以为某个数字还在使用中而跳过要么导致路径里残留着不属于当前分支的数字。我在帮人排查代码时发现最典型的错误就是只改了used数组却忘了path.pop结果所有结果都变成了同一根路径不断加长的快照。理解状态恢复还有一个更形象的角度把这棵树想成迷宫回溯就是“退回到岔路口再走另一条路”。如果不记得把走过的脚印擦掉后面的人也就是其他分支就会以为前面那条路已经被占了从而漏掉大量正确答案。3. 三种代码实现路线交换、used标记与迭代生成3.1 路线一交换法原地修改nums数组交换法是很多教材喜欢用的实现方式核心思路是不额外维护一个路径数组而是直接在当前nums上做两次swap把某个数换到当前起始位置递归完成后换回去。def permute(nums): res [] def dfs(start): # 所有位置都已经固定记录当前排列 if start len(nums): res.append(nums[:]) return # 当前位置可以从 start..n-1 中选一个数 for i in range(start, len(nums)): # 选择把 nums[i] 换到 start 位置 nums[start], nums[i] nums[i], nums[start] # 进入下一层固定下一个位置 dfs(start 1) # 撤销选择换回来 nums[start], nums[i] nums[i], nums[start] dfs(0) return res这个写法的优势非常明显不需要额外的path数组也不需要used数组空间开销更小。它天然利用nums本身来记录排列状态。但代价是理解成本更高因为递归过程中nums数组的内容一直在变调试时如果打印每个分支的状态很容易被“为什么start位置不是原来的数了”搞晕。另一个特点是交换法生成的排列顺序并不是字典序。如果题目要求按字典序输出全部排列交换法需要配合排序或者在输出后统一排序否则可能不满足题意。同时也注意res.append(nums[:])必须拷贝直接append(nums)会让结果集里所有元素共用同一个列表对象。3.2 路线二used数组标记法逻辑最直白如果追求“一眼能看懂”我强烈推荐标记法。它用path数组记录当前路径上的数字用used数组标记哪些数字已经被用过递归时遍历整个nums跳过所有已使用的元素。def permute(nums): res [] path [] used [False] * len(nums) def dfs(): 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]) # 进入下一层 dfs() # 撤销选择 path.pop() used[i] False dfs() return res标记法的优点是选择列表非常明确“所有used[i]为False的数”。每次递归只需要看used数组不需要关心nums数组有没有被打乱。路径顺序和最终输出顺序也符合直觉——你按什么顺序遍历nums排列就会按什么顺序生成。它的缺点是多了两个额外空间path和used。在n很大时这个空间开销和结果数量相比其实微不足道所以绝大多数场景下标记法是更推荐的选择。我自己刷题和写教程时默认都用这个版本只有在面试官明确要求“原地完成”时才会切到交换法。3.3 路线三迭代生成与字典序思路除了递归回溯还有一种不讲递归的生成方式按字典序一步一步求出下一个排列。这个方法在“下一个排列”这道题里是主角当作全排列的完整解法也完全可以。思路是先对数组排序然后反复调用“找下一个排列”的过程直到不存在下一个排列为止。找下一个排列的经典步骤是从右往左找到第一个升序对(nums[i] nums[i1])然后从右往左找到第一个大于nums[i]的数nums[j]交换i和j位置最后把i1到末尾的部分反转。这个过程可以通过一个while循环反复执行不断产出新排列。在工程实践中Python自带的itertools.permutations已经封装好了全排列生成日常写业务代码时完全可以直接用。但在算法面试或刷题场景下我建议还是手写回溯。因为面试官考察的不是“你会不会调库”而是“你懂不懂递归和状态管理”。用库函数一步出结果反而没法展示解题思路。3.4 三种实现对比与选型建议用一张表把三者的关键差异列出来方便大家在面对不同题目时快速做选择。实现方式额外空间输出顺序理解成本适用场景交换法低原地修改非字典序偏高面试官要求原地、空间敏感used标记法path used按遍历顺序低通用场景最推荐迭代生成无递归栈字典序中需要字典序输出、或求下一个排列实际选型时我的经验是默认标记法因为可读性最好如果题目要求空间O(1)就换交换法如果要用字典序且不允许递归深度过大就上迭代法。三种写法都值得手写一遍写多了自然就明白各自的边界在哪里。4. 实际调试中的四个高频坑与完整排查链路4.1 坑一结果集里全是同一个列表这是一个非常经典的“新手段错误”。现象是输出的res长度正确但里面的每个排列内容一模一样全是最后一种排列。我第一次遇到这个问题时排查链路是这样的先在递归结束处加了一行print发现每次要append的path内容确实是不同的。那为什么res里的最终结果一样问题就出在res.append(path)而不是res.append(path[:])上。Python里列表是引用类型path变量指向的是同一个列表对象。回溯过程中path会不断被修改虽然每次append时path的内容是对的但这个对象在后续回溯中会被pop和append改变。由于所有res元素都是同一个对象的引用当整个递归运行结束path指向的那个列表已经变成了最后一种排列于是res里所有元素看起来都一模一样。修复很简单append(path[:])拷贝一份当前快照。这个坑在C里对应vector push_back(path)和push_back(path的拷贝)的区别在Java里对应add(new ArrayList(path))。凡是记录结果必须考虑是记录引用还是记录值。4.2 坑二used状态没有还原导致分支缺失现象输出结果数量不对通常比n!少。比如[1,2,3]只输出了两三种排列而且其中还夹杂着长度不到3的“半截排列”。排查时我发现了这样的代码used[i] True path.append(nums[i]) dfs() # path.pop() 忘了写 # used[i] False 忘了写如果只执行了used[i] True而没有在递归返回后恢复那么第一个分支走完后used里的标记全部为True后面的循环执行到任何i都会跳过整个递归树只展开了一束路径。如果path.pop忘了写路径只会越加越长递归结束条件永远无法触发最终要么栈溢出要么输出一堆不完整的组合。这类问题的排查链路很有规律先看结果数量再打印每个分支进入和退出时的path与used状态通常一眼就能看出“进入时选了什么退出时有没有还回去”。修复也很机械在递归调用返回后务必成对执行撤销操作。可以把“做选择”和“撤销选择”两行代码写在一起形成条件反射般的代码习惯。4.3 坑三交换法里swap的时机与下标越界交换法代码短但陷阱也不少。我自己调试时踩过的一个典型错误是在dfs(start)的for循环里写成dfs(i 1)而不是dfs(start 1)。为什么必须传start 1因为交换法基于一个前提区间[0, start-1]已经被前面的层固定好了当前层只需要决定位置start放哪个数。for循环枚举的是“把nums[i]换到start位置”换完以后我们应该去固定下一个位置也就是start 1。如果写成dfs(i 1)当i不是start时就会出现跳过中间位置的问题导致生成的排列长度错误或直接越界。还有一种情况是swap次数混乱。有的新手会在递归返回后忘记swap回来这样下一轮循环基于的是被上一轮修改过的数组产生的排列大量重复且错乱。排查手段是打印每次swap前后的数组内容确认“进入递归前换出去返回后换回来”是否严格成对。只要把交换法理解成“当前层和它管理的for循环共同负责位置start”下标问题就不容易再犯。4.4 坑四输入长度稍大就超时或内存暴涨严格来说这不是代码逻辑问题而是对输出规模没有预判。前面算过10个元素有3628800种排列每个排列如果作为独立数组保存内存占用轻轻松松上几百MB。很多在线评判平台的单个用例往往把n限制在8或者10左右就是为了让答案能完整保存下来。当你把n设为11、12去测时超时或者内存溢出都是正常现象不是算法写错了。遇到这种问题排查第一步不是优化代码而是检查题目约束。如果是自己做测试建议n不要超过10否则再优秀的回溯代码也会因为输出数量过大而卡死。如果题目本身允许n很大但要求返回结果那唯一的出路可能是改变返回策略比如改为生成器逐条产生排列或者只返回排列总数。这个坑提醒我们写代码之前先评估答案规模是一种非常实用的工程习惯。5. 一套回溯模板迁移组合、子集与N皇后5.1 抽象出通用回溯模板全排列的框架稍微抽象一下就能覆盖一大批高频回溯题。在我看来所有回溯题目都可以从三个维度去套模板结束条件怎么定义选择列表怎么生成状态怎么撤销。def backtrack(路径, 参数): if 结束条件: 记录结果 return for 选择 in 可选择的列表: 做选择 backtrack(更新后的路径, 新参数) 撤销选择接下来的重点就是看如何改这三处。组合题改的是选择列表的生成方式子集题改的是记录结果的时机包含重复元素的排列题改的是剪枝条件N皇后题改的是路径的数据结构和合法性检查。5.2 组合用startIndex压缩选择范围组合题通常要求从n个数中选出k个不考虑顺序。比如“从[1,2,3]里选2个数”结果是[1,2]、[1,3]、[2,3]而不是所有排列。它和全排列最大的区别是同一组数字不能因为顺序不同而重复出现。因此选择列表不能再是“所有没用过的数”而是“从某个下标开始的所有数”。做法是在dfs参数里加一个startIndex每层循环从startIndex开始并且递归传入i 1表示下一层只能选择更靠后的元素。def combine(n, k): res [] path [] def dfs(start): if len(path) k: res.append(path[:]) return for i in range(start, n 1): path.append(i) dfs(i 1) path.pop() dfs(1) return res这个startIndex其实就是组合题的核心它代替了used数组的部分功能只要保证后面选的数下标永远比前面大就不会产生重复组合。理解这一点组合题就只剩一个剪枝优化当剩余元素数量不够填满路径时提前返回。5.3 子集在递归过程中记录所有节点子集题和全排列、组合都不一样它要求输出所有元素的全部子集包括空集和全集。在决策树视角里全排列是只记录叶子节点组合是记录深度恰好为k的节点而子集是记录整棵树上的每一个节点。def 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这个写法非常简洁res.append放在递归函数开头而不是等到结束条件。这样空集、单元素子集、多元素子集都会被依次记录下来。很多人在理解子集时会卡一下“为什么这样就能不重不漏”其实和组合题的逻辑一模一样startIndex保证子集内元素的下标严格递增因此不会出现[1,2]和[2,1]这种重复表示。5.4 排列进阶重复元素去重怎么剪把全排列加上“数组可能包含重复数字”这个条件就变成了一道经典变体题。比如输入[1,1,2]正确输出只有3种排列[1,1,2]、[1,2,1]、[2,1,1]而错误的排列版本可能会输出6种其中包含大量重复。处理思路是先把数组排序让相同数字相邻然后在回溯的for循环里加一个剪枝条件。剪枝的核心判断是如果当前元素和前一个元素相同并且前一个元素在本层还没有被用过就跳过当前分支。nums.sort() used [False] * len(nums) 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]) dfs() path.pop() used[i] False这里有个容易混淆的点为什么条件是not used[i - 1]而不是used[i - 1]因为我希望同一层中相同数字只从最左边的那个开始尝试。如果前一个相同数字已经用过且被撤销说明它已经作为当前层的一个分支完整搜索过当前这个相同数字就不必再重复走一遍。如果前一个相同数字还在used状态说明我们在更深的层级中此时应该允许继续使用否则会漏掉像[1,1,2]里第二个1出现在排列第二位的情况。5.5 N皇后二维棋盘的状态校验N皇后问题看起来和排列毫无关系但它依然是同一套回溯模板。棋盘上的每一行相当于排列中的每一层每个皇后所在的列相当于这一层选中的数字。区别只在于合法性判断从“是否用过”变成了“和之前所有皇后是否冲突”。经典的优化做法是用三个数组分别标记列、主对角线、副对角线的占用状态。某个位置(row, col)如果被占用它所在的主对角线特征值是row - col副对角线特征值是row col这两个值在整张棋盘上都能唯一标识一条对角线。递归时逐行放皇后每次选择一列判断列和对角线是否冲突不冲突就占用并进入下一行回溯时再释放。def solve_n_queens(n): res [] board [[.] * n for _ in range(n)] col_used [False] * n diag1 [False] * (2 * n) diag2 [False] * (2 * n) def dfs(row): if row n: res.append([.join(r) for r in board]) return for col in range(n): d1 row - col n d2 row col if col_used[col] or diag1[d1] or diag2[d2]: continue col_used[col] diag1[d1] diag2[d2] True board[row][col] Q dfs(row 1) board[row][col] . col_used[col] diag1[d1] diag2[d2] False dfs(0) return res可以看到N皇后只比全排列多了一个“合法性判断”的环节。路径从一维列表变成了二维棋盘但“做选择、递归、撤销选择”的主干完全没变。这正好印证了前面那句话全排列模板吃透了迁移到其他回溯题只是改参数的问题。6. 从刷题到面试把全排列讲出层次感6.1 面试中的标准破题顺序如果面试中遇到全排列我的建议是不要在拿到题目后立刻写代码。可以先花几十秒把思路讲清楚顺序大概是先确认输入约束比如是否有重复元素、是否需要按字典序输出然后说“全排列本质是一棵决策树每个位置选择未被使用的数字直到所有数字都被选完”再说“我准备用回溯实现用一个path记录当前排列用一个used数组标记已使用数字递归结束时拷贝快照”最后分析复杂度。这个顺序看起来很简单但很多人在面试时因为太紧张直接把模板往白板上一默写结果面试官追问“你的used数组为什么在这里恢复”就答不上来。按先思路、再实现、后验证的顺序来反而显得思路清晰。哪怕代码有一两个小瑕疵面试官也会更愿意引导你修正。6.2 复杂度为什么是O(n * n!)全排列的时间复杂度有两个部分要算清楚。第一部分是递归树上一共会产生多少个节点。叶子节点有n!个从根到叶子的路径长度是n所以整棵树节点数量大致是n乘以n!的量级。第二部分是每到达一个叶子节点为了保存结果需要拷贝长度为n的路径数组这部分也是O(n)。因此总时间复杂度是O(n * n!)。空间复杂度要从三部分看递归栈深度是npath数组长度是nused数组长度是n结果集占用的空间不计入算法本身的额外空间。所以额外空间复杂度是O(n)结果集空间则是O(n * n!)这是由输出规模决定的。如果面试问“能不能优化”通常回答是结果集必然占用这么多空间代码使用的辅助空间已经可以做到O(n)没有更优的排列生成方式能把结果数量变少。6.3 常见延伸问题全排列的变体很多面试官经常会在此基础上追问。第一个是“下一个排列”它不再要求输出全部只要求按字典序求出某个排列的下一个排列解法就是我前面介绍的迭代思路。第二个是“带重复元素的全排列”核心就是排序加used[i-1]判断的剪枝。第三个是“排列中的第k个”可以结合阶乘数系统来做进一步考察对阶乘结构的理解。第四个是“字符串全排列”本质和数组全排列完全一样只是把数字换成字符。我在准备面试时通常会把这几道题连着刷一遍。因为它们共享同一套决策树思想区别只是在于枚举规则和剪枝条件。把这些变体都理清楚后再遇到类似题基本不会慌。6.4 我的个人经验最后分享一个我自己的习惯每次讲全排列时我都会先在纸上画一个三层的小决策树把[1,2,3]的分支画出来然后指着树说“递归就是深度优先遍历这棵树回溯就是回到父节点重新走另一条分支”。这个图一画出来面试官基本就明白我已经掌握了回溯的本质后续追问的难度会明显降低。还有一个小技巧写代码时我会刻意把“做选择”和“撤销选择”两行代码放在同一缩进层次紧挨着写中间只隔一行递归调用。这样在review时能一目了然地检查状态是否成对出现。很多新手漏掉path.pop就是因为在代码里把它们隔得太远视觉上根本没形成“对称”的暗示。这个习惯帮我避开了不少低级错误也推荐给大家。