代码随想录算法训练营打卡第25天今天这三道题让我把回溯算法的“去重”彻底想通了。491递增子序列、46全排列、47全排列II看似一个子集变种加两个排列模板实际上是在逼你回答同一个问题你到底在“同一层”去重还是在“同一条树枝”去重很多同学包括我自己在组合问题里靠一套i startIndex nums[i] nums[i-1]走天下到了491发现不能排序直接傻眼到了47又发现同样的去重写法还能写出两种语义。这篇文章就把三道题的思路、代码、坑一次性讲清楚适合正在刷回溯、想弄明白去重本质的朋友直接参考。1. 三道题的定位与整体思路拆解1.1 为什么代码随想录把这三题安排在一起先看题目本身。491.递增子序列给你一个整数数组找出所有长度至少为2的递增子序列子序列要求保持原数组相对顺序但题目数组不一定有序而且明确规定不能对原数组排序。这是什么概念我们熟悉的子集问题第一件事往往是排序因为排序后重复元素相邻去重只需要比较nums[i] nums[i-1]。491把这个捷径堵死了逼你用另一种方式处理重复在本层用一个哈希表记录已经选过的元素值。46全排列就更有意思了。前面刷的组合、子集问题递归参数里都有个startIndex作用是不回头地往后选。但排列是“排队”{1,2}和{2,1}是两个不同结果所以选择列表永远是整个数组只是已经放进当前路径的元素不能再选。这里引入了used数组这是排列类问题的标志性结构。47全排列II则是把排列和去重放在一起考。输入数组里有重复元素输出排列不能重复。你需要先排序然后用used数组同时完成“排除已选元素”和“剪掉重复排列”两件事。三题从子集变种到标准排列到排列去重难度层层递进每一题都迫使你从“套模板”走向“理解模板状态”。我自己的体会是回溯算法的模板就那几行真正的分水岭全在对“选择列表”和“去重范围”的理解上。把这三题连起来看你能看到同一个模板是怎么随着问题场景微调的。1.2 回溯模板的本质路径、选择列表、终止条件无论什么回溯题核心都是递归遍历一棵决策树。树上的每个节点代表一个“当前状态”从根到某个节点的路径就是已经做出的选择。你需要做三件事维护路径path、构造选择列表for循环遍历、设定终止条件什么时候把路径加入结果。标准模板长这样void backtracking(参数) { if (终止条件) { 收集结果; return; } for (选择 : 本层选择列表) { 处理节点; backtracking(递归参数); 回溯撤销; } }这个模板的威力在于它把“暴力枚举”变成了“有策略的暴力”。491和46、47的区别只在于“本层选择列表怎么构造”。组合问题用startIndex保证不回头子集问题同样用startIndex但收集所有节点排列问题用used标记已选元素子序列问题在组合问题基础上额外判断“递增性”。生活化类比组合像是朋友聚会握手甲和乙握过一次就不再重复所以每次从下一个人开始排列像是排队拍照每个人都可能站在不同位置所以每一层都要遍历所有人的剩余位置子序列像是在一条队伍里挑人但不能打乱队形而且必须越挑越高去重则是为了避免把“两个相同身高的人”当作两个不同选择输出两遍。理解了这个框架后面所有看似复杂的判断都只是在这个框架上增加“剪枝条件”。2. 核心细节解析与实操要点2.1 491递增子序列不能排序时的本层去重491最反直觉的地方在于你不能排序。因为一旦排序原数组的相对顺序就丢了选出来的就不是“子序列”而是“子集”。比如[4,6,7,7]排序后变成[4,6,7,7]恰好有序容易误导换个例子[4,7,6,7]排序后[4,6,7,7]你可能会找出[4,6,7]但原数组中6在7后面[4,6,7]根本不是原序列的子序列这就是错误。那怎么去重思路是在同一层递归中如果有两个相同的值第一个值已经把以它为开头的所有子序列都枚举完了第二个值再枚举一遍必然产出重复结果。由于元素值范围是[-100, 100]总共201个可能值我直接用bool used[201]标记“本层是否已经用过这个值”。注意这个数组是在backtracking函数里作为局部变量定义的每层递归都会创建一份新的所以它只管“当前层”不管祖先层。判断递增也简单如果path不为空且path.back() nums[i]说明当前选择会破坏递增性直接跳过。这里有个容易忽略的点path.back()只是路径的最后一个元素不需要和之前所有元素比较因为之前的递增性已经由上一层的递归保证了。还有一个重点是终止条件。494是子序列不是固定长度所以不是“长度等于多少”才收集。正确的做法是只要当前path长度大于等于2就先把path加入结果然后继续往下递归。比如[1,2,3]走到[1]时不收集继续走到[1,2]收集再到[1,2,3]也收集。这样能用同一个递归过程输出所有长度的递增子序列。完整代码我会在第3章给出这里先记两条铁律一不能排序二本层去重用哈希或数组不用相邻比较。2.2 46全排列为什么排列不用 startIndex进入排列题很多人的第一反应是我也用startIndex从startIndex开始遍历不就行了不行因为组合和排列的核心差异在于“顺序是否敏感”。组合里[1,2]和[2,1]是同一个结果所以用startIndex强制只能往后选保证不会出现逆序组合排列里[1,2]和[2,1]是两个结果必须允许在每一层重新考虑所有元素。于是引入used数组。used[i] true表示nums[i]已经在当前路径path中本轮递归不能再选。递归进入下一层时for循环还是从头遍历所有下标但通过if (used[i]) continue;跳过已选元素。这样第一个分支会先选nums[0]然后下一层再选nums[1]得到[1,2]回溯后第一层选nums[1]然后下一层再选nums[0]得到[2,1]。终止条件也很自然当path.size() nums.size()说明所有元素都放进来了这就是一个完整排列加入结果后返回。为什么一定要等长度相等因为排列必须包含每个元素恰好一次不存在“子排列”这种说法。时间复杂度直觉排列数量是 n!而每一层都要遍历 n 个元素判断used所以整体是 O(n * n!)。这个复杂度看着吓人但回溯本就是解决小规模枚举问题的n 一般不超过8到10配合剪枝完全可用。这里有个实操建议初学阶段老老实实用used数组法先理解“选择列表 所有未使用元素”这个模型。不要急着学通过swap原地交换的优化写法虽然它省了辅助空间但思路跳跃容易把状态搞混。2.3 47全排列II树层去重才是真去重47是46的升级版nums里有重复元素比如[1,1,2]。如果不做任何处理你会得到6个排列但其中[1,1,2]会因为两个1的先后顺序不同出现两次实际只应有3个。所有去重的核心问题都是**什么时候两个选择会产生一模一样的结果**答案当当前层已经处理过某个值的元素后面再遇到相同值时后续递归的子树和之前完全一致。这种重复发生在“同一层”的不同分支之间叫“树层去重”。继续用[1,1,2]演示。排序后数组是[1(第一个), 1(第二个), 2]。第一层有两个选择选第一个1或者选第二个1。选第一个1后第二层还能选第二个1得到[1,1,2]选第二个1后第二层还能选第一个1得到的也是[1,1,2]。这两个分支产出的所有排列集合是一模一样的所以第一层的第二个1应该被剪掉。关键代码是if (i 0 nums[i] nums[i - 1] !used[i - 1]) continue;为什么是!used[i-1]used[i-1]表示“前一个相同元素是否在当前路径上”。如果used[i-1] true说明我们正处在一条已经选择了前一个相同元素的树枝上比如已经选了第一个1现在递归到下一层准备选第二个1这是合法的因为排列里确实可以有两个1不能剪。如果used[i-1] false说明前一个相同元素不在当前路径上且我们已经回溯到了同一层此时再选当前元素就属于“同一层的第二个相同选择”必须剪。打个比方树层去重是“哥哥已经把所有路走完了弟弟不要再走一遍”树枝去重是“哥哥走在前面弟弟跟在后面队伍里两个人都要有位置”。两种都是一种剪枝思路但树层去重才能保证结果集合不重复也最符合直觉。另外注意47必须先排序因为nums[i] nums[i-1]这种相邻比较依赖相同元素排在一起。排序不会影响排列结果因为排列本来就可以任意顺序输出排序只是改变了输入的顺序最终排列集合不变。3. 实操过程与核心代码实现3.1 491递增子序列完整实现下面给出完整可运行的 C 代码我用的是数组代替哈希表性能更好class Solution { private: vectorvectorint result; vectorint path; void backtracking(vectorint nums, int startIndex) { // 长度大于等于2就收集但不return因为还要继续向后延伸 if (path.size() 1) { result.push_back(path); } // 本层去重表每层递归都会新建所以只影响当前层 bool used[201] {false}; for (int i startIndex; i nums.size(); i) { // 递增性判断当前元素必须不小于路径最后一个元素 if (!path.empty() nums[i] path.back()) { continue; } // 本层相同值已经选过跳过 if (used[nums[i] 100]) { continue; } used[nums[i] 100] true; 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; } };这里有几个边界细节。第一used[nums[i] 100]是因为数值范围是[-100, 100]加上100映射到[0, 200]。第二!path.empty()防止空路径时调用path.back()造成未定义行为。第三数组used在backtracking函数体内声明意味着每一层递归都有自己独立的去重记录这正是“本层去重”的正确实现。如果你错误地把used放在成员变量里那会变成“全局去重”导致很多合法结果被丢掉这是很多人踩过的坑。时间复杂度最坏情况是 O(2^n * n)因为数组有 n 个元素时所有递增子序列最多是 2^n 级别复制每个结果到result又要 O(n)。空间复杂度 O(n)主要是递归栈和path。如果想用通用写法也可以用unordered_setint替代数组代码逻辑一样只是哈希表有额外开销。实际提交时数组版本明显更快。3.2 46全排列完整实现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]) { // 路径中已经包含nums[i] 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; } };这段代码再次体现排列和组合的区别for循环总是从i 0开始而不是startIndex。used数组保证了不重不漏。很多人问为什么path.pop_back()之后还要used[i] false因为回溯的本质是“恢复现场”。当前分支结束后必须把标记清掉让下一分支重新拥有选择权。如果把used[i] false忘掉递归会越走越深但永远选不了新元素结果就是只能生成一个排列。调试这个题目有个好方法在backtracking入口打印path在返回前也打印一次观察递归进出的顺序。你会发现它就是在深度优先遍历一颗排列树每一条从根到叶子的路径都是一个排列。3.3 47全排列II完整实现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]) { continue; } // 树层去重当前元素和前一个相同且前一个不在当前路径上 if (i 0 nums[i] nums[i - 1] !used[i - 1]) { 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; } };主函数里多了sort这是整个去重逻辑的基石。你可以试着手动模拟[1,1,2]第一层 i0 选第一个1进入递归i0被used跳过i1的1因为used[0]true而前面条件!used[i-1]为 false所以可以通过得到分支[1,1,2]接着 i2选2得到[1,1,2]后回溯。再回到第一层i1时used[0]已经是 false且nums[1]nums[0]满足剪枝条件跳过i2选2得到[2,1,1]。最终只会有3个结果。很多人尝试把剪枝条件改成used[i-1] true也能通过所有测试用例。这是因为树枝去重和树层去重都能保证结果不重复只是剪枝的时机不同效率略有差别。但从理解角度我强烈推荐!used[i-1]版本因为它直观对应“同一层不要重复开头”的语义而且在以后处理更复杂的排列题时不容易出错。3.4 三题在模板上的差异对比题目问题类型选择列表构造去重手段终止条件491.递增子序列子序列组合变种startIndex向后选加递增判断本层哈希/数组记录已用值路径长度≥2即收集不返回46.全排列标准排列所有未使用元素used过滤无重复元素不需要去重路径长度数组长度47.全排列II排列去重所有未使用元素used过滤先排序树层相邻相同值剪枝路径长度数组长度这张表基本就是回溯题目的一个分类地图。遇到新题先判断是组合、子集、子序列还是排列再套相应的选择列表构造方式最后问自己“重复结果是怎么产生的”就能快速定位剪枝条件。我自己刷题时会把每道题按这四列填进表格横向对比比单纯刷量管用得多。4. 常见问题与排查技巧实录4.1 491最大的坑顺手排序导致结果错误我在训练营群里看到最多的问题就是“为什么我的491输出了一堆不在原序列里的子序列”。点开代码一看基本都是先对nums做了sort然后按照子集题的写法在for循环里用nums[i] nums[i-1]去重。排序后元素虽然相邻了但原数组的顺序信息全部丢失。子序列的定义要求保持原数组相对顺序排序等于把“队伍打乱重新排队”选出来的当然不是子序列。正确的处理方式是把“值相等”的去重和“顺序递增”的判断分开顺序递增用nums[i] path.back()判断值相等去重用本层used[201]记录。这两件事互不干扰。如果实在想用哈希表也要用unordered_setint每层新建不能全局复用。还要注意题目中的“递增”是允许相等还是不允许相等。491明确要求“递增子序列”即[1,2,2]是递增的非严格递增所以我的代码只判断nums[i] path.back()也就是当前元素小于路径最后一个元素时才跳过。如果你写成就会漏掉相等元素组成的合法子序列这是另一个隐藏错误。4.2 去重时 i startIndex 与 i 0 的适用场景组合、子集问题的去重条件经常写成if (i startIndex nums[i] nums[i - 1]) continue;排列类问题则写成if (i 0 nums[i] nums[i - 1] !used[i - 1]) continue;为什么一个用startIndex一个用0因为组合问题里for循环是从startIndex开始的比较“当前元素和前一个元素是否在同一层相邻”只需要保证i startIndex即可不需要关心nums[startIndex-1]。排列问题的for循环每次从0开始所以用i 0比较当前元素和数组中前一个元素。什么时候可以不用相邻比较当题目不允许排序时比如491相邻比较失效只能退回到哈希表记录“本层已取值”。所以去重手段的选择其实是受“能否排序”约束的。遇到新题先问自己能不能排序能就用排序相邻比较不能就用本层哈希。这是最快决策路径。4.3 used数组传引用还是传值的隐蔽bug递归函数参数里used必须传引用void backtracking(vectorint nums, vectorbool used)如果写成vectorbool used按值传递那每一层递归都会拷贝一份完整的used数组你在当前层的修改只影响拷贝不会影响上层递归中已经设置好的状态。结果就是递归进去时used始终是初始的全 false排列永远选不齐所有元素或者产生大量重复。这个问题非常隐蔽编译不报错运行结果却千奇百怪。我在排查这类错误时会先检查递归函数的参数列表凡是需要“跨递归层共享状态”的变量used、path、result要么传引用要么放成员变量。path如果传值每层都会复制一份路径虽然结果可能对但内存和时间爆炸。这里推荐统一风格path和result设为类成员变量used传引用这样代码最清晰。4.4 性能优化与调试技巧回溯题 n 一大就超时所以在正确的前提下性能优化也很重要。第一个优化是用数组替代unordered_set491里bool used[201]比unordered_setint快一个量级。第二个优化是尽早剪枝比如47中如果当前元素和上一个元素相同且上一个元素未使用直接跳过这本质上是把“将要重复的一整棵子树”砍掉。第三个优化是减少不必要的复制result.push_back(path)会复制一次这是必要的但path本身不要频繁拷贝。调试时我最常用的工具不是 IDE 断点而是日志。在递归入口打印当前startIndex或i、path内容、used状态在回溯点也打印一行。这样能直观看到“进入分支→回溯→进入下一分支”的过程比脑补快得多。比如47的输出日志你会发现第二个1在第一层被跳过时日志里没有进入下一层递归这正好验证了剪枝条件生效。4.5 刷题节奏与我的个人体会从491到46再到47我把同样的模板写了三遍最大的收获不是记住了代码而是终于分清了“结果去重”和“搜索顺序去重”。491告诉我不要一上来就排序先看题目到底在说什么46告诉我排列的组合结构是“未使用元素集合”不是“后面的元素”47告诉我去重要回答“重复的根在哪一层”树层剪枝才是正解。如果你现在正卡在回溯上我的建议是不要把三道题当三道题刷而是当作“一个模板的三种参数配置”去对比。多画树形图少背代码尤其要把used数组在每个节点的值画出来。我用了一个很笨但有效的方法把[1,1,2]的所有排列手写一遍再对照代码里的剪枝条件一个个打勾之后全排列II就再也难不倒我了。这个习惯一直保留到现在遇到复杂去重题我就先写小例子再套模板至少省一半调试时间。