今天刷到算法训练营第十八天题单里开着三道题491.非递减子序列、46.全排列、47.子集II。这里必须先说一个题号问题LeetCode 第47题其实叫全排列 IIPermutations II并不是子集II。真正叫子集II的是第90题。所以这篇笔记里我把47按全排列 II 来讲。三道题放在同一天刷特别有意思因为它们都在反复练同一件事回溯过程中哪些分支该剪、该用什么方式剪。491是不排序场景下的去重46是排列的基础模板47是排列里的重复元素去重。把这三道题吃透回溯里的“去重”基本就入门了。如果你正在跟代码随想录的训练营或者准备面试遇到回溯题这篇文章可以当一份补充笔记看。我不光会贴能跑的代码还会把为什么这样做、哪些写法容易踩坑一起说清楚。1. 这三道题到底在练什么1.1 回溯模板先立在这回溯算法本质上就是一个带剪枝的递归所有回溯题都长一个骨架void backtracking(参数) { if (终止条件) { 收集结果; return; } for (选择本层集合中的元素) { 处理节点; backtracking(路径, 选择列表); 撤销处理; } }区别只在于三个地方终止条件是什么、每层从哪里开始选、怎么去重。491、46、47这三道题正好把这三个地方的常见变体都覆盖了。先说终止条件。子集问题通常是“每个节点都收集”组合问题是“叶子节点收集”排列问题是“path长度等于原数组长度时收集”。491属于子集类所以每进入一层递归只要当前path长度不小于2就先把path加入结果。46和47属于排列类所以只有path填满时才收集。再说每层从哪里开始选。组合和子集用startIndex保证后面的选择不会回头比如选了2之后不会再选1。排列不用startIndex因为排列里1,2,3和2,1,3是两种不同结果每一层都从下标0开始选但要用used数组标记哪些元素已经在当前path里被用过了。这三点搞清楚三题的框架就都有了。1.2 组合、子集、排列怎么区分很多人刷题的时候会把组合、子集、排列混在一起其实判断标准很直接组合顺序不重要结果里没有顺序差异比如[1,2]和[2,1]是同一个组合。子集也是顺序不重要但要求输出所有节点不只要叶子。排列顺序重要[1,2]和[2,1]是两个不同结果。对应到回溯代码上组合和子集用startIndex控制起始位置排列用used数组配合从头遍历。再往下一层就是去重问题。组合和子集里常见的“重复”是同一层出现相同数值的分支比如数组[1,2,2]第一层选了第二个2和选第一个2最终都会得到一堆重复子集所以要在树层上去重。排列里的重复除了同一个元素不能重复使用之外还要处理相同数值在不同位置上的重复分支比如[1,1,2]的第一个位置选第一个1和选第二个1会生成同样的排列这也要在树层上去重。1.3 一个必须提前说清楚的题号问题再强调一次看到“47.子集II”不要直接开写子集代码。LeetCode的47题是Permutations II中文名全排列 II。子集II是另一道题题号90。代码随想录训练营第十八天的安排通常是491、46、47这三道所以这里的“子集II”大概率是笔误。如果真想刷子集II它的去重逻辑和47的全排列II有相似之处但又因为子集用startIndex、排列用used数组细节上完全不同。题目名称这种东西刷的时候最好对一眼英文名不然很容易把模板记串。2. 491 非递减子序列不让排序去重反而更纯粹2.1 题目在说什么给定一个整数数组返回所有不同的非递减子序列每个子序列至少有两个元素。这里的“非递减”就是允许相等比如[4,6,7,7]里的[4,6,7,7]是非递减的因为7等于7。同时它强调是“子序列”也就是原数组里元素的相对顺序不能变。举个例子nums [4,6,7,7] 输出[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]注意这里只能出现一个[4,6,7]因为原数组里有两个7但你取第一个7和取第二个7得到的序列在数值上完全一样属于相同子序列要去掉。同时[4,7,7]和[6,7,7]是合法的因为你要得到两个7必须把原数组里的两个7都取上。2.2 为什么这道题不能先排序碰到子集去重很多人的第一反应是“排序然后用nums[i] nums[i-1]跳过”。但这个套路在491上不成立。因为题目要的是原数组的子序列如果你把原数组排序等于改变了元素之间的相对顺序会选出原数组里根本不存在的子序列。举个例子nums [4,7,6]。原数组中7在6前面所以[4,6]不是原数组的子序列。但排序后数组变成[4,6,7]如果按排序数组去找就会错误地输出[4,6]。这就是为什么491不能用排序去重法。那怎么办呢只能用另一种去重思路在同一层递归里用一个局部set记录“本层已经选择过的数值”如果当前数值在本层已经选过就跳过。这个set每层递归新建不需要回溯清空因为它只负责当前这一层的去重不管上层选了什么。这个细节很关键后面会仔细说。2.3 回溯函数怎么设计先确定参数数组nums、当前起点startIndex、当前路径path、结果集res。因为要的是子序列所以每层递归进入时只要path长度大于等于2就先收集结果。不需要额外的终止条件for循环跑完就自然结束了。单层逻辑里有两道判断我习惯按顺序写如果path不为空并且当前nums[i]小于path的最后一个元素说明加入后不是非递减子序列直接continue。如果本层的usedSet里已经出现过nums[i]说明相同数值的分支已经处理过直接continue。注意第一道判断里path不为空这个前置条件不能丢。path为空时你直接取path.back()会越界这在运行时是崩溃在面试时是扣分。完整C代码class Solution { public: vectorvectorint findSubsequences(vectorint nums) { vectorvectorint res; vectorint path; dfs(nums, 0, path, res); return res; } void dfs(vectorint nums, int startIndex, vectorint path, vectorvectorint res) { if (path.size() 2) { res.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]); dfs(nums, i 1, path, res); path.pop_back(); } } };这里有一个大家容易疑惑的点used是局部变量为什么不用在递归返回后执行erase因为局部变量在每次调用dfs时都会重新创建它只存在于当前这一层递归的for循环生命周期里。比如第一层循环里选了4used里有4等递归进入下一层新一层dfs又创建了一个新的used此时上一层的used对下一层没有任何影响所以下一层依然可以选4。这正是我们想要的不同层可以重复选择相同数值因为子序列允许连续多个相同值比如[4,6,7,7]里面两个7分别来自不同层。而同一层不允许重复选相同值因为同一层重复选相同值会产生重复分支。2.4 这题的常见坑第一个坑是试图“优化”掉set。有人觉得只判断nums[i] path.back()就行不需要set。但问题在于同一层可能出现两次相同值且都满足非递减条件。比如nums [4,7,7]第一层选了第一个7后会递归出以[4,7]开头的所有子序列第一层再选第二个7时又会递归出完全一样的[4,7]分支。没有set就去重不干净。第二个坑是把used定义成成员变量并且在递归返回后调用used.erase。一旦这样写去重范围就从“同一层”变成了“所有祖先层加起来”会误伤一些合法分支。最典型的就是[4,7,7]会少掉[4,7,7]因为第二层想选第二个7时发现第一层已经用过7了就不让选。这个错误很隐蔽跑几个用例可能还发现不了。第三个坑是只收集path.size() 2的结果。题目要求所有长度大于等于2的非递减子序列不是只收集长度为2的所以收集条件必须是path.size() 2。第四个坑是对负数和越界范围的处理。题目的nums[i]范围是[-100, 100]如果你愿意可以用大小为201的bool数组替代unordered_set这样更快一点bool used[201] {false}; // 去重时判断 used[nums[i] 100]用数组时要记得加偏移100不然负数下标直接崩。用unordered_set就不用管范围写法更简单性能也足够。我日常刷题更喜欢set因为不用记偏移量。3. 46 全排列没有重复数字时回溯最清爽的样子3.1 排列和组合的本质区别第46题给一个不含重复数字的数组比如[1,2,3]返回所有全排列。全排列中[1,2,3]和[2,1,3]是两个不同答案所以不能用startIndex。startIndex的作用是“强制后面的选择只能从当前位置之后开始”这在组合和子集里是对的因为[1,2]和[2,1]是同一个子集。但排列里你选了1之后下一个位置还可以选2或3也可以在某条分支里先选2再选1所以每一层都要从下标0开始扫描所有元素。那怎么避免同一个元素被重复选进同一个排列靠used数组。used[i]表示下标i对应的元素是否已经在当前path里。如果已经用过直接跳过。3.2 回溯实现直接给出C代码class Solution { public: vectorvectorint permute(vectorint nums) { vectorvectorint res; vectorint path; vectorbool used(nums.size(), false); dfs(nums, used, path, res); return res; } void dfs(vectorint nums, vectorbool used, vectorint path, vectorvectorint res) { if (path.size() nums.size()) { res.push_back(path); return; } for (int i 0; i nums.size(); i) { if (used[i]) { continue; } used[i] true; path.push_back(nums[i]); dfs(nums, used, path, res); path.pop_back(); used[i] false; } } };围绕这段代码有三个点值得讲清楚。第一处理节点是“标记used[i] true 把元素放进path”撤销处理是“path.pop_back() used[i] false”这两步必须对称。有些新手会把used[i] false写在递归之后但要先pop还是先重置顺序搞错。其实顺序不影响结果只要都在递归返回后执行即可。我习惯先pop再resume used符合直觉。第二for循环里没有startIndex每一层都从0开始。这就是排列和子集在代码结构上最明显的区别。你写排列题的时候如果发现自己在传startIndex就要停下来想一想是不是把它当组合题做了第三终止条件是path.size() nums.size()因为全排列必须把所有元素都用完。如果提前收集结果比如path长度为1就push那就变成求排列前缀了不是本题要求。3.3 used数组隐藏的一个小细节used数组的作用范围是“当前递归路径”不是“当前层”。所以在每一层递归里只要下标i的元素还在path中就不能再选。这其实是在同一树枝上去重不允许一个元素在同一分支上重复出现。这里可以和491的局部set对比一下。491的set只负责同一层去重不能跨层46的used数组要跨层保留所以定义在递归函数外面并且递归返回后要手动回溯到false。一个是“本层临时记录”一个是“全局路径占用记录”这是两个完全不同的东西别混。另外46题因为数组没有重复数字所以不存在“相同数值不同下标”造成的重复排列问题。但这个题干净的模板直接为47题铺好了路。47题只要在46的基础上加上一道对重复数值的树层剪枝就够了。4. 47 全排列 II重复元素去重排序 used 双条件4.1 题目和示例第47题是全排列 II输入数组里可能包含重复数字。比如nums [1,1,2] 输出[[1,1,2],[1,2,1],[2,1,1]]如果不做任何去重朴素回溯会给出6个排列其中以1开头的有4个但两个1本质上分为“第一个1在开头”和“第二个1在开头”两种分支结果一模一样。所以需要去掉这种重复。最优解法是先排序然后在回溯里加一个剪枝条件if (i 0 nums[i] nums[i - 1] used[i - 1] false) { continue; }这个条件很多人第一次看都会懵为什么要判断used[i - 1] false为什么不能写成used[i - 1] true我一开始也在这个地方翻过车后来发现必须把它放到递归树里看才清楚。4.2 为什么去重条件是 used[i-1] false先记住结论在排列去重里用used[i - 1] false做的是树层去重也就是“同一层相等元素只取第一个”用used[i - 1] true做的是树枝去重会漏解。用[1,1,2]举个例子。先排序nums[0] nums[1] 1。看第一层递归i从0开始。i0时选第一个1path [1]进入下一层。等这个分支全部跑完回溯回到第一层此时used[0]已经被重置为false。然后for循环走到i1nums[1] nums[0]如果此时used[0] false成立continue跳过不会产生以第二个1开头的重复分支。这就是树层去重第一层选了第一个1之后就不允许再选第二个1开头。那为什么不写成used[0] true呢因为在第一层i1时used[0]已经是false了条件不成立它就不会跳过于是会出现两个以1开头的重复大分支。这就不对。再往下看一层。当path [1]已经选了下标0的1进入第二层递归used[0] true。第二层i0时used[0]为true跳过i1时nums[1] nums[0]且used[0] true。如果去重条件写的是used[i - 1] true这里就会continue导致你永远选不了第二个1最终漏掉[1,1,2]这个排列。而used[i - 1] false的条件在这里是false不会continue所以能正确地把第二个1选进来。总结成一句话遇到相同元素时used[i - 1] false表示前一个相同元素是在同一层被试过但已经回溯掉了说明当前分支是重复分支剪掉used[i - 1] true表示前一个相同元素正在当前路径上说明这两个相同元素可以在同一条排列里同时出现不能剪。4.3 完整实现class Solution { public: vectorvectorint permuteUnique(vectorint nums) { sort(nums.begin(), nums.end()); vectorvectorint res; vectorint path; vectorbool used(nums.size(), false); dfs(nums, used, path, res); return res; } void dfs(vectorint nums, vectorbool used, vectorint path, vectorvectorint res) { if (path.size() nums.size()) { res.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]); dfs(nums, used, path, res); path.pop_back(); used[i] false; } } };这里有一个容易忽略的小点去重剪枝里不能写nums[i] nums[i - 1]之后直接continue而不看used[i - 1]的状态。比如同一树枝上前一个相同元素正在被使用此时你是允许选当前元素的否则[1,1,2]会被剪掉。所以必须加上used[i - 1] false这个条件。还有一个常见的变体写法if (i 0 nums[i] nums[i - 1] used[i - 1] true) { continue; }这种写法在LeetCode某些题解里也出现过但它通常配合另一个条件或特定递归顺序使用很容易让人混淆。我的建议是面试和日常刷题都统一用used[i - 1] false因为这个条件最贴合“树层去重”的定义你画一次递归树就能验证它是逻辑完备的。4.4 如果不排序能不能用set去重也可以。比如在每一层递归里定义一个unordered_set记录本层已经选择过的数值遇到重复值就跳过。但这对全排列来说不够干净因为全排列本身已经依赖used数组管理“哪些下标被用过”再叠加一个set等于同时维护两套去重逻辑反而更容易出错。排序 used数组的写法更统一性能也更好。只有在491那种不能排序的题目里才被迫使用每层set。5. 三个题刷完去重这件事才算真正入门5.1 怎么一眼看出是树层去重还是树枝去重刷完这三道题我最大的收获是学会分清楚两个问题这个问题是“同一层不能选重复值”还是“同一路径不能重复使用同一个元素”491的set解决前者46、47的used数组同时解决后者和前者。组合和子集里去重主要发生在树层。因为同一路径上元素只会被选一次你不需要担心同一个元素在当前path里重复出现startIndex已经保证了不会回头。排列里因为你每层从头扫描必须用used数组防止同一个下标在当前路径里重复出现这就是树枝去重。而重复数值造成的重复结果发生在树层于是还要排序 used[i - 1] false来再剪一刀。以后遇到回溯题先画一层递归树标出哪些分支会产出相同结果然后问自己这些重复分支是在同一层还是在同一路径上这个问题的答案直接决定去重代码怎么写。5.2 状压DP和枚举子集什么时候才需要最近很多人刷题会看到“状压DP 枚举子集”这种说法。它的经典代码长这样for (int sub mask; sub; sub (sub - 1) mask) { // sub 是 mask 的一个非空子集 }这个循环可以枚举某个集合的所有子集。如果你想统计一个数组有多少个满足某种性质的子集或者判断某个子集是否存在N又比较小通常N 20状压DP确实比分步回溯更高效。但今天这三道题尤其是491要求输出具体子序列不只要求数量回溯依然是最直观、最好写的方案。状压DP适合“计数、可行性、最优值”这类问题回溯适合“输出所有方案”的枚举问题。遇到热词里的“状压DP”不要慌先用题目要求判断方案类型再决定要不要套状态压缩。5.3 一些我踩过的坑和答题节奏最后整理几个实战中容易翻车的点491的局部set不要定义成全局的也不要手动erase。它是每层临时变量负责“本层相同数值只处理一次”。46和47的used数组必须定义在递归函数外面并且要回溯成false。它记录的是“当前路径上的占用情况”。47的剪枝条件used[i - 1] false不要写成used[i - 1] true。判断依据是前一个相同元素在当前层已经被用过但已经释放说明这个分支是重复的。子集类题目收集结果放在递归函数开头组合和排列类题目收集结果放在终止条件里。491收集条件是path.size() 246和47收集条件是path.size() nums.size()。写回溯代码时递归返回后一定要记得pop_back。漏掉这一步路径会越堆越长结果全错。我见过很多次这种情况排查到最后就是pop_back写丢了。另外说一个面试技巧碰到回溯题可以先跟面试官说“我先画一下递归树”然后把树层去重和树枝去重分开讲。比如491你就说“这题不能排序所以我用每层的set做树层去重”47你就说“这题先排序再用used做树枝占用判断加used[i-1] false做树层去重”。能把这些说清楚比闷头写代码更容易拿高分。我个人刷完这三道题后的体会是去重题最大的难点不在代码而在“你知不知道自己在哪个维度上去重”。一旦把树层和树枝分开491的set、46的used、47的排序加used本质上没有一个新东西。后面再遇到类似题目我都是先写出回溯框架再想清楚“这两刀该砍在哪一层”基本就不会错了。这份笔记就当给你排掉我当年踩过的雷希望能帮你少走点弯路。