1. 回溯算法三连击从子序列到全排列的层层递进打卡第25天回溯专题终于进入“排列类”题目的环节。前面我刷过组合、分割、子集今天遇到的这三道题基本概括了回溯算法在“排列”场景下的全部常见考法491递增子序列看的是“约束条件下的子集枚举”46全排列看的是“最标准的有序排列模板”47全排列II看的则是“去重逻辑和剪枝时机”。如果你同时刷过组合总和II和子集II你会明显感觉到今天这三题里的去重思路和之前的树层去重一脉相承但同时又各自多了一个陷阱。很多同学做到第47题时会发现明明思路看着和40题组合总和II差不多怎么一写就错这就是因为排列和组合在最底层的“选数逻辑”上完全不同——组合用的是startIndex来约束剩余可选元素而排列需要每一层都从头扫描、配合used数组标记已选元素。这个差异理解透了回溯题才算真正入门。今天这篇文章我把自己刷这三道题时走过的弯路、对比过的解法和总结出来的速记口诀都整理一遍特别适合正在跟训练营的伙伴、以及刷了一部分回溯题但总在去重和边界条件上卡壳的同学阅读。开始之前先把三题的定位列清楚后面每一道我单独拆开细讲491 递增子序列子集框架 同一层去重但不能排序46 全排列排列框架 used数组标记无重复元素47 全排列II排列框架 used数组标记有重复元素所以既要树枝去重又要树层去重三题互为递进建议按顺序刷完。2. 491.递增子序列不能排序的时候怎么去重2.1 题目到底在问什么给定一个整数数组nums找出并返回所有该数组中不同的递增子序列递增子序列中至少有两个元素。举个例子nums [4, 6, 7, 7]输出结果里不能包含两个一模一样的[4, 7]同时子序列必须保持原数组的相对顺序不能重排。第一次看到这个题很多人包括我的第一反应是这不就是子集问题吗按照回溯老套路先把数组排序然后在同一层判断nums[i] nums[i-1]就跳过再在收集结果时判断一下是否递增完事。我也确实是这么写的但跑了一遍用例之后直接发现问题——这题不能排序。因为子序列要求保住原有相对位置比如[4, 6, 7, 7]排序后变成[4, 6, 7, 7]看似一致但如果来一个[4, 7, 6, 7]排序后就变成[4, 6, 7, 7]原来不存在[4, 6]这个子序列排序之后竟然出现了。排序破坏了原数组的顺序信息子序列对顺序的敏感性决定了这条路走不通。2.2 同一层去重的正确姿势set既然不能排序那传统nums[i] nums[i-1]的写法就失效了。我们需要一种不依赖排序的去重手段。很多教程直接给出答案在每一层的递归中定义一个unordered_setint当遍历某一层的候选元素时如果这个元素已经被本层用过就跳过。这样在同一递归深度不可能出现两个相同的选择分支。为什么用 set 就能解决因为去重的本质是“同一个位置不能选重复的值”。排序法是通过相邻元素比较来实现这点set 则是靠哈希记录历史选择来实现两者不冲突只是应用场景不同。这里有个非常重要的细节unordered_set必须定义在每一层递归内部而不是全局变量。它只保证“树的同一层”不选重复元素而不同层之间完全可以选相同的值。放在函数内层递归到下一层就自动创建新的 set天然实现层间隔离不需要手动清理。补充一句这里也可以用一个局部bool used[201]数组替代因为本题数值范围是 -100 到 100做个偏移即可速度比 set 更快代码也不复杂。但训练营教程标准答案用 set先用 set 把逻辑理清楚进阶时再用数组优化。2.3 递增判定和剪枝条件收集结果时要求当前路径path中至少有两个元素并且最后一个元素大于等于path的最后一个元素才允许加入path。换句话说在递归入口除了“先判断当前 path 是否满足条件并收集”之外进入横向遍历时对每个候选元素还要做一次递增判定如果nums[i] path.back()不满足递增直接跳过如果nums[i]在本层 set 中已经出现过直接跳过。这样纵向递归和横向遍历双重约束下每一层的选择都会被严格过滤。有个小细节值得注意递增子序列题目里“递增”定义为非递减也就是允许[1, 2, 2]这种带相等元素的子序列。判断时要注意用而不是写反了会漏掉相等值的合法组合。我第一版就用跳过导致[1, 2, 2]没被收集查了半天才发现是边界写错。2.4 C参考实现与复杂度class Solution { private: vectorvectorint result; vectorint path; void backtracking(vectorint nums, int startIndex) { if (path.size() 1) { result.push_back(path); } unordered_setint used; for (int i startIndex; i nums.size(); i) { if (!path.empty() nums[i] path.back()) { continue; } if (used.find(nums[i]) ! used.end()) { continue; } used.insert(nums[i]); path.push_back(nums[i]); backtracking(nums, i 1); path.pop_back(); } } public: vectorvectorint findSubsequences(vectorint nums) { result.clear(); path.clear(); backtracking(nums, 0); return result; } };时间复杂度方面每个元素在每一层都有选与不选两个分支最坏情况是 O(2^n * n)n 是数组长度path 复制到 result 需要 O(n)。空间复杂度是递归栈深度 O(n)。实操中我建议调试时打印每一层的path和used能直观看到 set 是层间隔离的。2.5 一个实际踩过的坑set 定义在哪一层刚刷这题时我把unordered_setint used定义成了类的成员变量结果跑出来大量重复结果。原因很简单回溯递归会回到上一层如果 used 是全局的之前层的选择记录会“残留”到当前层导致相同值被误判为重复而剪掉结果漏解、重复解并存。这个问题不看 debug 输出真的很难发现。后来我随手在递归入口打印 set 的 size才意识到每层都应该从零开始。这个错误特别隐蔽建议刷题时遇到“结果集莫名少了一些分支”的情况优先检查这类“看似局部实则全局”的变量。3. 46.全排列为什么排列必须用used数组3.1 排列和组合的底层差异先看题目要求给定一个没有重复数字的序列nums返回其所有可能的全排列。[1, 2, 3]的输出中[1, 2, 3]和[2, 1, 3]是两种不同的排列。而在组合类问题里例如求三数组合[1, 2, 3]和[2, 1, 3]会被视为同一个组合因此只保留一个。这个本质区别直接决定了回溯逻辑组合问题用startIndex控制遍历起点第 i 层从 i1 开始选天然保证“后面的元素只在后面选”从而避免乱序组合重复排列问题中每个位置都可以选数组中的任意元素所以递归每层必须从i 0开始遍历但要用一个used数组或布尔数组记录“当前路径已经选了哪些下标”同一路径内避免重复选同一个元素。通俗点说排列就像往一排格子里填数字每个格子都可以从全部数字里选但填过数字的格子不能再填组合则是从队伍里挑人挑完一个只能往后继续挑不会再回头。3.2 递归终止条件和收集时机排列的终止条件非常直观当path.size() nums.size()时所有数字都用完了把path加入结果返回。这个写起来很简单但初学者容易忽略一点因为排列的每一层遍历范围都是整个数组如果不用used做标记递归时会无限递归如先选1再选1再选1……直到栈溢出。所以used数组的两重作用必须理解清楚纵向约束进入下一层时标记为 true 的下标不可再选保证一个数字不会在同一路径中重复出现撤销逻辑递归返回后把used[i]改回 false让同一层的下一个分支可以重新选择该数字。这里和组合类问题的startIndex恰好形成对照组合靠 startIndex 隔离“前面的元素”排列靠 used 隔离“路径中已选元素”。3.3 标准解法与优化点class Solution { private: vectorvectorint result; vectorint path; void backtracking(vectorint nums, vectorbool used) { if (path.size() nums.size()) { result.push_back(path); return; } for (int i 0; i nums.size(); i) { if (used[i] true) continue; used[i] true; path.push_back(nums[i]); backtracking(nums, used); path.pop_back(); used[i] false; } } public: vectorvectorint permute(vectorint nums) { result.clear(); path.clear(); vectorbool used(nums.size(), false); backtracking(nums, used); return result; } };一个可行的优化是当提前知道某分支不可能产生有效排列时直接跳过。但本题没有重复元素也没有额外约束所以无需剪枝。排列类题目中剪枝通常在“有重复元素 要求去重”的47题中出现也就是下一道题的核心。这里我还想多提一句“为什么全排列的复杂度是 O(n!·n)”。因为排列数量本身就有 n! 种每种排列复制进结果需要 O(n) 时间。很多新手纠结回溯过程为什么这么慢其实在 n 不大时没问题一旦 n 到 10 以上n! 就会暴涨到 3628800配合复制开销已经很难跑完更别说 n 到 15。所以回溯类题目通常 n 都很小看到大范围数据基本可以判断题目另有思路。3.4 从组合模板切到排列模板的思维转换刷题过程中我总结了一句口诀“组合用 startIndex排列用 used组合收集叶子排列也收集叶子但排列的叶子就是满了的 path。”这句话帮我少走了很多弯路。在46题之前我连续刷了组合总和、分割、子集模板非常固化。结果第一次写全排列时自然而然地写了startIndex然后发现输出只有[1,2,3]一种排列。这不是编码问题是思路没转过来组合里 startIndex 是为了防重复组合排列里需要的是“每个位置都能回头选”。另外排列不需要先排序因为无重复元素时排序除了增加开销对结果没有影响。只有当题目出现“重复元素且结果去重”时排序才会作为去重的辅助手段登场。4. 47.全排列II排序used才是去重黄金搭档4.1 有重复元素之后问题立刻变得复杂题目描述给定一个可能包含重复数字的序列nums返回所有不重复的全排列。对比46题唯一变化是数组里可能有重复数字。比如nums [1, 1, 2]标准排列是 6 种但[1a, 1b, 2]和[1b, 1a, 2]在数值上都是[1, 1, 2]必须去重。去重的难点在于我们不能简单地“遇到相同的数就跳过”因为不同位置上的相同数字可能在同一个排列中同时出现一个排列里必须包含两个1。真正要去重的是“在树的同一层横向扩展时不重复选择值相同的元素”。这句话怎么理解递归树的每一层代表“当前这个位置放哪个数字”。如果nums[0]和nums[1]都是 1那么它们放在同一个位置上产生的排列是一样的比如第0位放nums[0]1和第0位放nums[1]1后续路径完全相同结果必然重复。所以同一层必须二选一只放一次。但纵向递归到下一层时如果第一个1已经在 path 中那么第二个1完全可以选择因为两者在同一个排列里的不同位置此时结果是合法且不重复的。这就是“树层去重”和“树枝去重”的经典区分。4.2 排序到底为了方便什么排序的核心目的让重复元素相邻。重复元素相邻后在一层遍历时只需检查“当前值是否和前一个值相同”并且“前一个值是否已经被使用过通过 used[i-1] 判断”就可以决定是否跳过当前元素。这里的判断条件大家在网上会看到两种写法if (i 0 nums[i] nums[i-1] used[i-1] false) continue; // 写法A if (i 0 nums[i] nums[i-1] used[i-1] true) continue; // 写法B两种写法都能通过但语义上有微妙差别。对于写法Aused[i-1] false表示同一层的横向去重因为上一个相同元素在横向遍历中已被选择过并回溯撤销所以 used[i-1] 为 false此时如果再选当前元素就会和上一个分支产生重复。对于写法Bused[i-1] true表示树枝上的绝对去重前一个相同元素已经出现在当前路径上那当前元素就不能再选这其实是在纵向维度上禁止了重复值的“连续使用”。那么到底哪种写法更正确、更符合训练营的主流思路用“层”的视角分析最清晰回溯到同一层时used[i-1]应该是 false因为递归返回时已经把标记撤销了此时用写法A判断used[i-1] false是合理的剪枝而递归到下一层时used[i-1]可能是 true因为上一层的相同值仍在该层的 path 中但此时我们不希望去重——下一层本来就应该允许选第二个1。那为什么两种写法都能通过因为写法B虽然逻辑上是在做树枝去重但放到本题数据条件下遇到used[i-1] true的场景恰好出现在树层去重需要剪枝的节点附近结果碰巧也能得到正确答案。实操建议训练营和相关题解统一使用写法A也就是used[i-1] false时跳过。理由很简单当上一个相同元素没有被使用说明是同层这个才是真正的横向重复如果上一个元素被使用了说明是在路径上当前元素恰好可以选不应该被剪掉。4.3 两个版本的完整代码先看写法A推荐参考的版本class Solution { private: vectorvectorint result; vectorint path; void backtracking(vectorint nums, vectorbool used) { if (path.size() nums.size()) { result.push_back(path); return; } for (int i 0; i nums.size(); i) { // 树层去重同一层相同元素只取第一个分支 if (i 0 nums[i] nums[i - 1] used[i - 1] false) { continue; } // 树枝去重同一个排列中不能重复用同一个下标的元素 if (used[i] true) { continue; } used[i] true; path.push_back(nums[i]); backtracking(nums, used); path.pop_back(); used[i] false; } } public: vectorvectorint permuteUnique(vectorint nums) { result.clear(); path.clear(); sort(nums.begin(), nums.end()); vectorbool used(nums.size(), false); backtracking(nums, used); return result; } };再看不排序的写法用每层新建 set 也能去重但排序used整体性能更好且思路更统一下面这种 set 写法用来辅助理解可以不建议作为主写法// 不排序的版本每次递归新建 unordered_set 记录本层已取过的值 class Solution { private: vectorvectorint result; vectorint path; void backtracking(vectorint nums, vectorbool used) { if (path.size() nums.size()) { result.push_back(path); return; } unordered_setint layerUsed; for (int i 0; i nums.size(); i) { if (used[i] || layerUsed.count(nums[i])) continue; layerUsed.insert(nums[i]); used[i] true; path.push_back(nums[i]); backtracking(nums, used); used[i] false; path.pop_back(); } } public: vectorvectorint permuteUnique(vectorint nums) { result.clear(); path.clear(); vectorbool used(nums.size(), false); backtracking(nums, used); return result; } };结论排序 used[i-1] false 是回溯去重的最稳方案推荐记忆这套写法因为组合总和II、子集II也都通用。4.4 去重维度对比为什么同一层去重不等于全局去重很多新手会把“同一层去重”误以为“只要值相等就跳过”。为了说清这一点我们再拿[1, 1, 2]举例第一层第0位选第一个1。进入下一层第1位不能选第一个1已经 used但可以选第二个1。此时 path [1, 1]这是合法的排列前缀。第一层选第二个1时由于nums[0] nums[1]且used[0] false第一个1已被回溯撤销按照写法A直接跳过。这样第一层永远不会产生“第0位放第二个1”的重复分支。如果错误地写成used[i-1] true时跳过在第一层选第二个1的场景下used[0]是 false所以不跳过会产生一个与“第0位放第一个1”完全重复的分支结果中就会出现两个相同的[1,1,2]。只有在特定递归时机下巧合弥补才让写法B免于出错。这一步的“为什么”吃透了去重就不再是玄学。4.5 三道题放在一起看模板对照表为了便于复习我把三题的模板参数整理如下题目是否排序去重方式遍历起点终止条件附加剪枝491 递增子序列否题目约束每层 setstartIndexpath.size() 1 收集递增判断46 全排列否无无重复每层 i0path.size() nums.size()used 防重复选同一下标47 全排列II是排序 used[i-1]每层 i0path.size() nums.size()used 防重复选同一下标 树层去重这张表在我复盘时非常有用。特别是“是否排序”这一列491是绝对不能排序47是必须排序同样是去重两者在排序上的态度完全相反搞混了题目就废了。5. 实战调试心得这些坑我全踩过一遍5.1 忘记撤销 used 标记导致结果莫名爆炸46和47题里最容易犯的低级错误是递归前used[i] true递归后忘记used[i] false。表象结果中途正常后面出现大量重复或缺失排列程序甚至可能栈溢出。排查建议在每次递归调用前后打印path和used数组。如果发现某个分支结束后进入另一个分支时 used 还是全 true基本就是撤销写漏了。回溯算法的核心心法就是“递归前做选择递归后撤销选择”这两个操作是一对要写在一起。5.2 491题里把 used 做成全局变量之前已经说过这题每层的 set 必须局部创建。我还想强调一个记忆技巧所谓“同一层去重”其实每次横向循环中收集的是“本层已尝试过的值”该层循环结束这个 set 就没有存在意义了所以放在函数体内部天然合理。当成全局变量用虽然单靠局部清理也能实现但多一个清理步骤就多一个出错点。5.3 排列题里错误使用 startIndex在这三题之前我连续刷的都是组合类手指条件反射般写成backtracking(nums, i 1, used);这在46题里会漏掉大量排列。例如[1,2,3]第一层选了1第二层从2开始选就永远不会出现[1,3,2]。全排列的本质是“每一层都可以回头选以前没选过的数”所以只能用used判断而不是用 i1 限制。有一个过渡技巧如果你实在分不清该用哪个先问自己“如果这一步选了某个数下一步还能不能选排在它前面的数”能就用 used不能就用 startIndex。5.4 491题递增判断写错边界再补充一个细节有些题解在递归开头写if (path.size() 1 path.back() nums[i])这是把递增判断混进横向循环里的写法思路一样但注意nums[i]是在path非空时与path.back()比。推荐在 for 循环开头就写上if (!path.empty() nums[i] path.back()) continue;这是习惯问题但至少可以减少一次无效递归。5.5 关于剪枝的定位思考回溯的剪枝有两种横向剪枝同一层跳过某些元素和纵向剪枝提前终止不可能的分支。491题的递增判断属于横向剪枝47题的used[i-1] false属于横向剪枝而used[i] true本质上是纵向约束防止同一路径重复选同一元素。分清这两类剪枝阅读别人代码时会快很多自己写时也不容易混淆去重条件。6. 训练营打卡节奏的一点个人体会从第20天左右开始回溯算法的题型密度明显加大组合、分割、子集、排列四类问题一个接一个。如果你跟我一样是边工作边刷题很容易在某一天产生“今天题目做出来了但脑子一片空白”的错觉。到了第25天这个节点我的建议是放慢一天专门做一个横向总结把组合总和II、子集II、递增子序列、全排列II拉出来对比一次。很快就能发现刷题到最后其实就是在比对“去重条件”和“遍历起点”。正式因为这样我在写这篇打卡总结时把三题的模板差异放在最前面讲把每一题的“为什么这么做”放在代码前面。如果只是把代码抄一遍下一次遇到变种题照样不会那打卡就失去意义了。今天之后回溯算法还剩棋盘类问题N皇后、解数独没刷这两类题会从一维递归升级到二维递归但核心依然是“选择 撤销选择”的循环。基础打牢之后那个坎不会太难。更细节的做题感受是最近几天我用“模板速写”的方式练题看到题目先不急着写代码在草稿纸上回答三个问题——第一这题属于组合/分割/子集/排列中的哪一类第二需不需要排序第三去重放在哪一层三个问题回答完代码基本就是套模板的事。这个流程推荐给大家试试。最后再分享一个小技巧46题的全排列使用迭代写法其实有现成的next_permutation函数可以直接调刷题阶段尤其训练营里不建议依赖库函数。自己手写一遍回溯全排列才能真正理解递归状态切换的过程。等彻底掌握回溯之后的性能优化才有基础。打卡第25天结束明天继续棋盘问题的魔鬼训练。