今天是代码随想录算法训练营的第十八天打卡内容依然是回溯专题而且是三块硬骨头491.非递减子序列、46.全排列以及47题你题单里写的“47.子集||”我猜大概率是47.全排列II毕竟46和47是一对儿排列双胞胎就算你真的排的是90.子集II去重思路也能无缝迁移。这三道题放在同一天刷我觉得是训练营故意安排的——它们把回溯算法里最容易翻车的两个点全部暴露出来了一是“去重到底去的是哪一层”二是“选择空间到底由谁控制”。如果前面几天的组合总和、子集问题你已经刷得比较顺那这三道题就是你从“会写回溯”到“真的懂回溯”的分水岭。先说结论这三道题刷完我对递归的理解从“套模板”变成了“画树形图再翻译成代码”。尤其是491那道题它打破了我对“去重必须先排序”的惯性认知而46和47则让我彻底搞明白了 used 数组和 startIndex 各自的作用边界。这篇文章我会把三道题的完整思路、代码实现、复杂度推导、常见坑点全部分享出来最后再聊一个延伸话题为什么子集枚举是通向状压DP的必经之路。适合正在刷代码随想录或者准备面试回溯类题目的朋友阅读。1. 回溯三板斧从491到46再到47差在哪里1.1 回溯函数的“三件套”写法回溯算法说穿了就是一棵树的深度优先遍历。每一层递归解决一个位置的“选择”选择完之后递归进入下一层返回时撤销选择这就是大名鼎鼎的“回溯三件套”void backtracking(参数) { // 1. 终止条件满足时收集结果 // 2. for 循环遍历候选列表 // 3. 递归前做选择递归后撤销选择 }很多初学者容易把注意力放在“模板本身”但真正拉开差距的是三个问题终止条件在哪里写for 循环的起点是什么哪些状态需要撤销这三道题刚好把三种情况都覆盖了。491 非递减子序列收集结果发生在递归入口而且不 return因为每一个非叶子节点都是一个合法结果。46 全排列收集结果发生在叶子节点path.size() nums.size()必须 return。47 全排列II收集结果的位置和 46 相同但多了“同层去重”的逻辑。这三处差异不是靠背模板能解决的必须理解每个问题的“合法结果到底出现在树的哪个位置”。1.2 组合、子集、排列的选择空间差异回溯的本质是“枚举所有可能性”但不同题型对“可能性”的约束不同最核心的约束有两个元素能不能重复选、集合内元素顺序有没有关系。题型控制候选范围的变量收集结果的时机典型题目组合startIndex限制下一层只能往后选叶子节点77.组合、216.组合总和III子集startIndex限制只能往后选每个节点78.子集、90.子集II排列used 数组限制同一路径内不能重复选叶子节点46.全排列、47.全排列II为什么组合和子集用 startIndex排列用 used 数组因为组合不关心顺序[1,2] 和 [2,1] 是同一个结果如果下一层还从头开始选必然产生重复。排列关心顺序[1,2] 和 [2,1] 是两个不同的结果所以每层都要从头遍历所有元素但同一路径上不能重复选同一个下标所以需要 used 数组来标记“这个位置的元素已经用过了”。这个对比表建议大家存下来我刷到第十八天最大的感受就是回溯题不是一道一道背的是按“题型家族”来理解的。一旦分清了组合、子集、排列三类问题的控制变量后面遇到什么组合总和III、递增子序列、字符串排列都只是在基础模板上做增删。2. 491.非递减子序列不能排序的同层去重实战2.1 题目隐藏条件保留原顺序导致排序去重失效先看题目给你一个整数数组 nums找出并返回所有该数组中不同的递增子序列递增子序列中至少有两个元素且不需要连续。示例[4,6,7,7] 的输出里不能有重复的 [4,7]。第一反应肯定是“这不就是子集问题吗先排序然后用之前的同层去重写法”。如果你真这么做了恭喜你踩中了这道题最大的坑排序会改变元素之间的相对顺序排序之后你就不是在找“子序列”而是在找“子集”了。举例说明。数组 [4,6,7,7] 中子序列必须保持 4 在 6 前面、6 在 7 前面这个原始顺序。如果排序成 [4,6,7,7] 好像没区别但如果输入是 [3,4,2,3]合法的递增子序列有 [3,4]、[2,3]、[3,4?] 等排序后变成 [2,3,3,4]枚举出的 [2,3,4] 在原数组中根本不是一个子序列因为原数组中 2 在 4 的后面。所以491 这道题绝对不能排序。这就带来一个连锁问题之前 90.子集II 的去重依赖“排序后相邻元素比较”现在不能排序了怎么去重2.2 用set做同层去重别让path被重复元素污染答案是在每一层递归中维护一个无序集合只记录“本层已经使用过哪些值”。注意是“本层”不是“整条路径”。代码长这样class Solution { public: vectorvectorint result; vectorint path; void backtracking(vectorint nums, int startIndex) { // 注意收集结果不能return因为还要继续往后取值形成更长的子序列 if (path.size() 1) { result.push_back(path); } unordered_setint usedSet; // 只负责本层去重不需要回溯删除 for (int i startIndex; i nums.size(); i) { // 剪枝保证非递减 if (!path.empty() nums[i] path.back()) { continue; } // 去重本层已经用过这个值跳过 if (usedSet.find(nums[i]) ! usedSet.end()) { continue; } usedSet.insert(nums[i]); path.push_back(nums[i]); backtracking(nums, i 1); path.pop_back(); } } vectorvectorint findSubsequences(vectorint nums) { backtracking(nums, 0); return result; } };这里最反直觉的地方在于** usedSet 不需要在递归返回后 erase**。很多新人会习惯性地写usedSet.erase(nums[i])觉得“选了就要撤销”。但注意这个 set 的作用是防止同一层出现重复取值而每一层递归都会创建一个全新的 set递归返回后这个 set 就已经被销毁了。如果手贱加一行 erase反而会把“已经标记为使用过的值”重新放出导致同层重复。2.3 数组哈希优化-100到100的天然下标set 去重虽然直观但每次插入、查找都有哈希开销。491 这道题给了 nums 数值范围在 [-100, 100]总共 201 个可能取值完全可以用数组替代 setvoid backtracking(vectorint nums, int startIndex) { if (path.size() 1) result.push_back(path); bool used[201] {false}; // 下标偏移100存nums[i]是否用过 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(); } }实测下来数组哈希比 unordered_set 快不少而且代码更简洁。建议以后只要题目里出现“数值范围有限”优先考虑数组哈希。这个技巧在后面的哈希专题里也会反复用到。2.4 常见错误收集条件写在开头并return我一开始写这道题时脑子还停留在子集问题的模板里把代码写成if (path.size() 1) { result.push_back(path); return; // 这里错得离谱 }一旦加 return[4,6] 被收集后函数直接返回永远不会继续尝试 [4,6,7]、[4,6,7,7] 这些更长的子序列。正确的理解是一个递增子序列是另一个递增子序列的前缀前缀合法加上更多元素依然可能合法所以不能阻断向下递归。这个“收集但不返回”的模式在回溯里相对少见建议单独标记。3. 46.全排列从“选位置”到“选元素”的思维切换3.1 为什么排列题不用startIndex每层都是全量候选刷完组合再来做全排列第一感觉是“这模板怎么变形了”。全排列里[1,2,3] 和 [1,3,2] 是两个结果所以每一层循环都必须从头开始遍历所有元素不能像组合那样靠 startIndex 把候选范围锁在“当前元素之后”。那从头遍历不会重复选同一个元素吗比如在 path [1] 之后for 循环从头开始又会选到 1产生 [1,1,...]。这时就需要 used 数组登场。注意这里的 used 是“整条路径”级别的标记某个下标一旦被选入路径路径上任何一层都不能再选它。class Solution { public: 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; // 这个元素已经在路径里了 used[i] true; path.push_back(nums[i]); backtracking(nums, used); path.pop_back(); used[i] false; } } vectorvectorint permute(vectorint nums) { vectorbool used(nums.size(), false); backtracking(nums, used); return result; } };3.2 used数组的完整闭环标记、递归、回溯理解 used 数组的关键是理解它和 startIndex 的本质区别。startIndex 是“参数”每层递归通过传参确定候选起点used 是“状态”需要一路跟随路径走到叶子节点再逐步撤销。很多初学者会问为什么递归前要used[i] true递归后要used[i] false不撤销会怎样试想遍历 [1,2,3]第一层选了 1used[0] 变为 true。如果不撤销进入下一层时 used[0] 还是 true后面两层都不可能再选 1。当第一层继续尝试选 2 时如果 used[0] 没有在递归返回时复位说明“路径上已经存在 1”这个信息还在污染下一层状态后续所有分支都会少掉 1 这个选项最终结果集数量直接从 6 个缩水到 3 个。所以回溯里有一个金句递归前做什么递归后就要做对应的逆操作。选了就撤销标记了就复位。唯一的例外就是前面 491 那道题的 usedSet因为它是每层新建的局部变量生命周期只在本层天然不需要回溯。3.3 时间复杂度推导n! 与 n!*n 的关系面试官问到全排列复杂度不能只背一个 O(n!)。完整的推法是这样的第一层有 n 个选择第二层有 n-1 个选择第三层 n-2 个……所以要生成 n! 个叶子节点。每个叶子节点拷贝进结果集要 O(n)所以总时间复杂度是 O(n * n!)空间复杂度是 O(n)递归深度 path used 数组。这个推导思路同样适用于后面的 N 皇后只不过每层的候选数量会随列约束变化。复杂度不能只记结论要把“为什么”说清楚面试才有区分度。3.4 变形字符串全排列、n皇后类比字符串全排列就是把 nums 换成 s把数字比较换成字符比较核心逻辑一字不改。N 皇后则升级为二维棋盘但本质上还是排列问题的变体每一行选择一个列位置且这个列位置不能与之前所有皇后冲突。理解了全排列的 used 数组再去看 N 皇后里“列、两条对角线”的标记数组会发现套路完全相同。4. 47.含重复元素的全排列树层去重的分岔路4.1 排序让重复元素“排排站”used让去重“不误伤”47 题是 46 的升级版nums 可能包含重复数字但结果不能包含重复排列。比如 [1,1,2] 的全排列不能出现两个 [1,1,2]因为两个 1 交换位置后是一样的。这道题的核心思路是先排序让相同的元素相邻然后在回溯时利用 used 数组判断“当前这个元素是不是本层已经处理过的重复值”。完整代码class Solution { public: 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] false) { continue; } used[i] true; path.push_back(nums[i]); backtracking(nums, used); path.pop_back(); used[i] false; } } vectorvectorint permuteUnique(vectorint nums) { sort(nums.begin(), nums.end()); vectorbool used(nums.size(), false); backtracking(nums, used); return result; } };4.2 used[i-1]false与used[i-1]true到底差在哪这是整个回溯法里最容易混淆的一个问题至少我身边的人讨论过十次。先说结论在排列去重里两种写法都能得到正确结果但语义不同、效率也不同。// 写法A树层去重 if (i 0 nums[i] nums[i - 1] used[i - 1] false) continue; // 写法B树枝去重 if (i 0 nums[i] nums[i - 1] used[i - 1] true) continue;以 [1,1,2] 为例。used[i-1]false 的写法会在同一层循环里当第二个 1 被遍历到时发现前一个 1 没有被当前路径使用说明前一个 1 已经在其他分支用过或者即将被本层使用于是跳过。它的作用对象是“同一层兄弟分支”所以叫树层去重。used[i-1]true 的写法表示前一个 1 已经在当前路径上被使用如果现在再选当前这个 1就会产生同一条路径上两个相同值的重复所以跳过。它的作用对象是“一条树枝上的纵向重复”。为什么两种写法在排列题里都对因为排列题在每层循环都会遍历所有元素同一个值在本层可能被选中多次树层去重已经把重复“拦在门外”而树枝去重则把“路径上已有相同值”的情况拦掉。两者从不同角度避免了重复排列的产生。但更推荐 used[i-1]false因为它从源头砍掉了更多的重复分支剪枝效率更高也更符合代码随想录里的标准模板。4.3 如果题目是90.子集II模板怎么迁移如果你看到题单里写的是“47.子集||”而周末刷的确实是 90.子集II也不要慌它和 47 题的去重思想完全同源只是少了一个 used 数组。class Solution { public: vectorvectorint result; vectorint path; void backtracking(vectorint nums, int startIndex) { result.push_back(path); // 子集每个节点都收集 for (int i startIndex; i nums.size(); i) { if (i startIndex nums[i] nums[i - 1]) continue; // 树层去重 path.push_back(nums[i]); backtracking(nums, i 1); path.pop_back(); } } vectorvectorint subsetsWithDup(vectorint nums) { sort(nums.begin(), nums.end()); backtracking(nums, 0); return result; } };注意这里的去重条件写的是i startIndex不是i 0。因为子集题用 startIndex 控制本层起点只有“同一层内”的重复值才需要跳过从递归进入下一层后startIndex 变了判断也要跟着变。很多人在子集题里套排列去重的i 0结果把正常分支剪掉了。4.4 排列去重 vs 子集去重的本质区别排列去重和子集去重看着很像但控制的变量不同。排列需要 used 数组是因为每层的候选列表是“全量的”必须用 used 来区分“路径上已选”和“路径上未选”子集不需要 used因为 startIndex 天然保证不会回头选已经处理过的区间。去重动作本身针对的永远是“同一层重复值”但“同一层”的判断方式不同题型怎样界定同一层去重写法组合/子集靠 startIndexi startIndex nums[i] nums[i-1]排列靠 used 数组i 0 nums[i] nums[i-1] used[i-1] false这个表格建议贴在书桌前。我刷题时发现很多错误不是不会写代码而是“把上一道题的边界条件搬到下一道题”结果全盘崩溃。5. 延伸一击用二进制枚举子集通向状压DP5.1 回溯枚举子集 vs 二进制位掩码枚举刷完子集、排列你可能会想既然我可以用回溯枚举所有子集为什么很多算法题里还有“枚举子集”这种说法这里引出最近比较火的一个热词状压DP 枚举子集。回溯枚举子集是“一个一个走”复杂度 O(2^n)这里 n 是集合大小。二进制枚举完全等价用一个 n 位的数字 mask 表示一个子集mask 的第 i 位为 1 表示选取第 i 个元素。比如集合 [a,b,c]mask 101 表示选了 a 和 c。n 3 for mask in range(1 n): # 0 到 2^n - 1 subset [] for i in range(n): if mask i 1: subset.append(i) print(mask, subset)这个写法虽然看起来和回溯八竿子打不着其实它们枚举的树是一样的回溯的“选/不选”分支对应二进制位上的“1/0”。区别在于二进制枚举更适合做“状态转移”因为 mask 本身就是一个整数可以直接作为 DP 数组的下标。5.2 枚举子集的完整代码与剪枝技巧状压DP里经常要枚举“当前状态的所有子集”标准写法是for sub in range(mask, 0, -1): sub (sub - 1) mask # 下一个子集这里sub (sub - 1) mask是核心公式它的作用是跳过所有不属于 mask 的位快速枚举 mask 的子集。比如 mask 1011枚举出的子集依次是 1011、1010、1001、1000、0011、0010、0001。每一次减一再按位与保证遍历不重不漏。为什么这和回溯题相关因为回溯法枚举子集的时间复杂度是 O(2^n)而理想状态下应该只访问“合法子集”。在组合总和、N 皇后这类问题里回溯可以通过剪枝跳过大量不合法分支这是它优于裸二进制枚举的地方但反过来如果状态转移能从旧状态直接推出新状态比如 TSP 旅行商问题、集合划分问题状压DP就比回溯快得多。回溯擅长剪枝DP擅长复用两者的取舍就在这里。5.3 什么时候别用回溯状压DP的适用场景如果题目让你求解“最优解”而不是“所有解”且有明显的重叠子问题那就别硬套回溯。举一个典型的例子给一个数组问能否分成两个和相等的子集。回溯的思路是枚举所有子集找和为总和一半的那个时间复杂度 O(2^n)n30 直接炸而用状压DPdp[mask] 表示当前子集的元素和可以用递推快速判断n30 也能跑。这类题在代码随想录的DP章节会有更系统的讲解但你提前理解“子集枚举的状态压缩表达”后面学起来会快很多。6. 排坑实录这三道题我踩过的五个坑6.1 对非递减子序列排序结果全变子集了这是我在 491 上犯的第一个错误。拿到题想都不想就 sort然后按照 90.子集II 的去重逻辑写提交后一看用例 [4,6,7,7] 输出没问题换成 [1,3,2,4] 就多出 [1,2,3] 这种原数组里根本不存在的子序列。原因前面说过了子序列必须保持原顺序排序改变了元素之间的天然先后关系。以后凡是题目里出现“子序列”三个字先问自己一句能排序吗6.2 忘记对used数组回溯全排列只剩一条路我第一次写 46 的时候used[i] true是写在递归前的但递归后忘了恢复结果输出从 6 个排列变成 3 个。打印中间状态后发现第一层分支选完 1 之后used[0] 一直为 true导致后续所有分支都默认“第一个元素已经用过了”。这个错误的排查方法很简单在递归入口打印 path 和 used 数组一眼就能看出状态没有复位。推荐大家写回溯时先把“递归前操作”和“递归后逆操作”两行代码一起写上不要写一半再想。6.3 全排列II在递归入口去重自己和自己比47 题里容易犯的错误是把去重条件写成if (used[i] nums[i] nums[i - 1]) continue;这个写法的逻辑完全错乱。used[i] 表示“下标 i 是否已经在路径上”如果为 true 说明当前元素已经在 path 里直接跳过没错但加上nums[i] nums[i-1]后反而把“前一个重复值也在路径上”的正常情况一并跳过了结果导致 [1,1,2] 这种输入连合法排列都出不来。去重条件里的 used[i-1] 和循环里的 used[i] 是两个维度的判断不能混在一起写。6.4 递归参数引用与拷贝的坑写 491 时如果backtracking(vectorint nums)用值传递每层递归都会拷贝整个数组nums 长度为 15 以上时明显变慢改成vectorint nums后性能立刻好转。但要注意递归内如果对 nums 做了修改会影响所有层所以一般只读数组都用引用需要排序的数组在进入回溯前排序不要在递归里改。6.5 快速自查表检查项正确做法子序列/非递减子序列不做全排序用每层 set 或数组哈希去重子集/组合去重先排序用i startIndex判断同层重复排列去重先排序用used[i-1] false判断同层重复递归收集结果子集/递增子序列在入口收集不 return排列在叶子收集要 return撤销操作递归后 path.pop_back()used 数组复位每层新建的 set 不需要手动 erase最后再分享一个我自己摸索出来的小技巧。刷回溯题一定要先画树形图尤其是 47 这种带重复元素的题把 [1,1,2] 的画图画出来标上哪些分支是被剪掉的写代码时就会非常清楚。之前我偷懒跳过画图结果总在细节上反复出错后来每次做回溯前花三分钟画树代码基本一遍过。训练营第十八天刷题节奏已经进入后半程这时候比的不是谁刷得快而是谁复盘得透。这三道题值得二刷尤其是 491 那个“收集但不 return”的精髓还有 set 去重与排序去重的边界建议你用自己的语言总结一遍再输出成笔记那才算真正吃透。