如果让我只挑一道题来检验回溯算法和去重逻辑是否真正掌握我会选 Leetcode 491. 非递减子序列。这道题在 Leetcode 上标着中等难度但不少刷过 Leetcode 的人都会卡在它身上递归本身不难难的是“非递减子序列”这个表述背后藏着的几个坑——元素必须保持原始相对顺序、相同数值会产生重复结果、又不能像子集 II 那样先排序再相邻去重。无论你是准备面试、参加周赛还是单纯想把回溯这类题吃透这道题都很值得拆开揉碎地过一遍。今天我把当时的思路、踩过的坑以及最终可用的完整代码一起整理出来。1. 题目到底想考什么1.1 先别急着写递归把题意掰开揉碎给定一个整数数组nums返回其中所有可能的非递减子序列“非递减”的意思是序列中后一个元素大于等于前一个元素。还需要满足三个条件第一子序列不要求连续但必须保持原数组中的相对顺序也就是说你只能按原数组的索引从小到大去挑选元素第二结果中不能出现重复的子序列例如两个索引位置出现相同值最终只算一个结果第三子序列长度至少为 2空集和单元素都不能算进答案。比如官方示例输入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]]肉眼就能看出数组里有两个 7但答案中[4,7]只出现一次[6,7]也只出现一次。这就是这道题和普通子集题的核心差异你不仅要枚举所有合法选择还要在枚举过程中把“值相同、索引不同”导致的重复结果去掉。理解了这几个条件你应该能感觉到这不是单纯靠for循环能暴力搞定的问题。因为子序列的数量在元素个数较多时会呈指数级增长而每个元素都有“选”和“不选”两种状态天然适合用 DFS深度优先搜索加回溯去遍历整棵决策树。在 Leetcode 上这类考查“枚举所有组合 去重”的题目回溯基本是标准解法。1.2 回溯框架为什么是首选的思路用回溯做这道题的直觉来自一个非常朴素的决策模型从左到右扫描数组每遇到一个元素你有两种选择要么把它接进当前序列要么跳过它。只要保证接进去之后序列仍然是非递减的并且长度到达 2 就记录一次答案就能走遍所有可能性。这里有个细节很多人第一次写容易搞混对于“子序列”类问题DFS 的起点索引是在递增的如果你用startIndex控制遍历范围那么在递归里只看startIndex之后的元素天然保证了“相对顺序”。这个顺序约束不需要额外判断因为索引本身就是严格的次序。而且这道题的数据范围比较友好数组长度最多 15即使不去做任何复杂剪枝把所有合法子序列都枚举出来也不会超时。回溯算法在这道题上的核心价值不是“剪掉不可能的答案”而是“保证枚举过程可回溯、可去重”。所以如果你对回溯的模板还不熟悉这道题练习价值很大它能把 DFS 递归、路径记录、状态恢复、同层去重这几个基本功一次考到位。2. 去重这题真正的分水岭2.1 最隐蔽的误区不能先排序再相邻去重如果你先做过 Leetcode 90. 子集 II很容易形成一套肌肉记忆给定数组可能包含重复元素想求所有不重复的子集那就先排序然后在同一层递归里跳过相邻的相同值。这套方法在这题直接失效而且不是性能问题是逻辑错误。为什么因为子集不考虑顺序[3,1,2]和[1,2,3]在子集题目中被认为是同一个集合排序不影响结果。但子序列要求保持原数组中的相对顺序一旦排序原始索引关系就被打乱了。举个最简单反例nums [3, 1, 2] 排序后 [1, 2, 3]排序后DFS 会合法地生成子序列[2, 3]因为2在索引 13在索引 2排序后的顺序是 1→2→3。但在原数组[3,1,2]里2在索引 23在索引 0索引顺序是反的原数组中根本不存在[2,3]这个子序列。这个结果就是排序带来的脏数据提交上去必挂。所以491 这道题的去重逻辑不能建立在“改变元素顺序”的基础上只能另找思路。这也是它和 90 最大的区别90 是先排序再相邻去重而 491 必须在保持原始顺序的前提下在同一层递归里对“值”做去重。2.2 同一层到底要怎么去重回溯去重的一个核心概念是“同一层递归”。在 DFS 的for循环里每次循环进入的下一个兄弟节点都属于同一层它们共享同一个起点索引之前的状态。如果在这个for循环内部出现两个索引位置、但值相同的元素那么它们扩展出来的后续路径会高度雷同必须只保留第一个。实现手法很直接在每层for循环开始前创建一个只属于本层的去重集合used。每遍历到一个nums[i]先判断used里有没有这个值如果有就跳过如果没有就把它加入used再继续递归。这里有一个很多人纠结的点为什么used不用在递归返回后恢复因为used的使命是保证“当前层内不重复使用相同的值”它只对当前for循环负责。递归进入下一层后创建的是全新的used前一层用过什么值与下一层无关。所以如果used是 DFS 函数内部的局部变量就完全不需要手动撤销只有当你错误地把used写成成员变量或全局变量时才需要额外处理恢复逻辑这正好是后面要讲的常见 Bug 之一。2.3 手推 [4,6,7,7] 的递归树看清去重位置我们以[4, 6, 7, 7]为例手动走一遍 DFS 的第一层递归。第一层从索引 0 开始依次遍历4used没有加入used递归处理[4]开头的一系列子序列6used没有加入used递归处理[6]开头的一系列子序列第一个7used没有加入used递归处理[7]开头的一系列子序列第二个7used中已经有7直接跳过不进入递归。这样[7]开头这一大分支只被完整展开一次后续的所有重复子序列都被拦截在入口处。用used去重后第二条7不会再单独开一条分支这个分支里自然也不会产生重复的[7,7]因为[7,7]已经由“第一个 7 第二个 7”组合而成。但注意同一层去重并不会阻止跨层的重复元素组合。也就是说第二个7仍然会被后面的递归层使用。比如路径[4,7,7]中第二层的第一个元素是第一个7之后在第三层选择第二个7这时第二个7出现在第三层的for循环里而第三层的used是全新的里面并没有7所以[4,7,7]能正常生成。这就是局部used和全局“杜绝重复值”的本质区别局部去重只管同一层不管跨层。3. 三种语言的完整实现与细节解读3.1 C 版本用 bool 数组代替哈希集合在 C 里最常见的实现是用unordered_setint做本层去重但更推荐用定长bool数组。因为题目给出了数值范围是[-100, 100]总共才 201 种取值用bool used[201]的性能比哈希表高不少而且代码同样清晰。class Solution { public: vectorvectorint findSubsequences(vectorint nums) { vectorvectorint res; vectorint path; dfs(nums, 0, path, res); return res; } void dfs(const vectorint nums, int startIndex, vectorint path, vectorvectorint res) { if (path.size() 2) { res.push_back(path); } bool used[201] {false}; // 值域 [-100, 100]偏移 100 做索引 for (int i startIndex; i nums.size(); i) { int v nums[i]; if (used[v 100]) continue; // 同层值去重 if (!path.empty() v path.back()) continue; // 非递减检查 used[v 100] true; path.push_back(v); dfs(nums, i 1, path, res); path.pop_back(); } } };这段代码最需要注意的两行就是used[v 100]和v path.back()。前者负责拦截同层重复后者负责保证序列非递减。这里我特意把“检查非递减”放在“判断重复”的后面其实两者顺序无所谓因为这两个条件互不干扰但如果先查非递减遇到某些不满足条件的值可以更早跳过稍微省一点used的操作实测差距不大。3.2 Java 版本注意路径拷贝和数组初始化class Solution { public ListListInteger findSubsequences(int[] nums) { ListListInteger res new ArrayList(); dfs(nums, 0, new ArrayList(), res); return res; } private void dfs(int[] nums, int start, ListInteger path, ListListInteger res) { if (path.size() 2) { res.add(new ArrayList(path)); } boolean[] used new boolean[201]; for (int i start; i nums.length; i) { int v nums[i]; if (used[v 100]) continue; if (!path.isEmpty() v path.get(path.size() - 1)) continue; used[v 100] true; path.add(v); dfs(nums, i 1, path, res); path.remove(path.size() - 1); } } }Java 有个很容易遗漏的细节res.add(new ArrayList(path))必须拷贝一份新的列表否则后面path不断变化最终结果列表里的所有元素都会指向同一个引用。这类问题在 C 里不存在因为res.push_back(path)本身就是值拷贝但 Java 和 Python 都需要显式拷贝。3.3 Python 版本集合去重和切片拷贝from typing import List class Solution: def findSubsequences(self, nums: List[int]) - List[List[int]]: res [] path [] def dfs(start: int) - None: if len(path) 2: res.append(path[:]) used set() for i in range(start, len(nums)): v nums[i] if v in used: continue if path and v path[-1]: continue used.add(v) path.append(v) dfs(i 1) path.pop() dfs(0) return resPython 版本里used用集合代码最直观。有一点值得提path[:]是浅拷贝但这里path里的元素都是整数浅拷贝就足够安全。另外Python 的递归深度受限于默认递归栈但这题数组长度最多 15递归深度也就是 15 层完全不用担心栈溢出。3.4 一种备选思路二进制枚举加剪枝除了 DFS这题还可以用二进制枚举做。核心思路是用一个二进制掩码的每一位表示数组里对应索引的元素是否被选入子序列。例如mask 1010表示选第 0 个和第 2 个元素。由于数组长度不超过 151 15是 32768枚举所有掩码是可行的最后用集合去重即可。class Solution { public: vectorvectorint findSubsequences(vectorint nums) { int n nums.size(); setvectorint ans; for (int mask 0; mask (1 n); mask) { vectorint cur; bool ok true; for (int i 0; i n; i) { if (mask i 1) { if (!cur.empty() nums[i] cur.back()) { ok false; break; } cur.push_back(nums[i]); } } if (ok cur.size() 2) { ans.insert(cur); } } return vectorvectorint(ans.begin(), ans.end()); } };从代码量来看二进制枚举比 DFS 更短理解起来也比较直观。不过它需要把所有的 2 的 n 次方种掩码都遍历一遍即使有些掩码在很小的时候就发现不合法也要继续内部循环到末尾才能判断效率上不如 DFS。实际刷题时DFS 是更通用的答案二进制枚举可以作为复盘时的补充思路。3.5 两种思路的复杂度对比解法时间复杂度空间复杂度适用场景DFS 回溯O(2^n * n)每个合法路径最多 n 个元素拷贝进结果时需要 O(n)O(n)主要是递归栈和 path通用、推荐二进制枚举O(2^n * n)且无法提前剪枝O(2^n * n)主要是 set 存储数据量小、思路直观可以看到两种方法的时间复杂度都是指数级这在元素个数到 20 以内时问题不大。但面试中如果追问优化空间DFS 的剪枝能力会更受欢迎因为它可以在递归入口就把非递减约束失效的分支直接砍掉。4. 实战踩坑记录这四类 Bug 我全见过4.1 把“非递减”写成“严格递增”这是最典型的错误没有之一。很多题解里会强调“非递减”是但轮到自己写的时候手一抖就把判断条件写成了v path.back()时跳过也就是只允许严格变大的元素进入等于把题目改成了“严格递增子序列”。这个 Bug 最危险的地方在于用常规示例[4,6,7,7]测试时输出是[[4,6],[4,6,7],[4,7],[6,7],[7,7]][4,6,7,7]和[4,7,7]、[6,7,7]全部消失但题目示例要求必须保留这些“相等值重复出现”的序列。用[1,1,1,1]这类全相等数组测试时更容易暴露如果写成严格递增正确答案[1,1]、[1,1,1]、[1,1,1,1]一个都出不来。所以在本地写完代码后第一个测试用例就应该是[1,1,1,1]可以快速验证等值元素处理是否正确。4.2 used 数组生命周期写错全局变量导致的漏解我之前第一次独立写这题时顺手把used声明成了类的成员变量想着复用一个数组省点内存。结果测试[4,6,7,7]时输出少了[4,7,7]和[6,7,7]。原因很简单全局used的状态跨越了不同层的递归。以[4,6,7,7]为例当你按正确 DFS 走到路径[4,7]时在第三层需要尝试选第二个7才能生成[4,7,7]。但如果used是全局的第二层加入第一个7时把used[7]标记成 true这个标记没有在递归返回后清除第三层for循环遇到第二个7时就会误以为“本层已经出现过 7”从而跳过。结果就是所有包含两个7的结果全部漏掉。要修复这个 Bug要么把used移入 DFS 函数内部让它成为每层独立的局部变量要么坚持全局used但必须在递归返回时执行类似used[v 100] false的恢复操作。我个人推荐前者局部变量最不容易出错而且编译器优化得很好性能几乎无损。4.3 忘记恢复 path 的状态回溯的本质是“递归前做选择递归后撤销选择”。如果你在递归返回后没有执行path.pop_back()或path.remove(...)那这条路径上的元素会像叠罗汉一样越攒越多产生大量错误的子序列。比如下面的错误代码path.push_back(nums[i]); dfs(nums, i 1, path, res); // 忘记 path.pop_back();测试时你会发现输出里出现很多超过 15 个数长度的“子序列”而且内容完全不符合非递减约束。这个 Bug 用肉眼最容易发现只要打印一下path看到它里面积累的元素数量超过数组长度说明撤销动作丢了。4.4 忽略“至少两个元素”的边界这道题要求子序列长度至少为 2所以res.push_back(path)必须放在path.size() 2的判断里。如果把判断去掉结果会把空集和所有单元素序列也收进去提交直接判定不通过。我见过有人把判断放在递归入口处也就是一开始就if (path.size() 2) res.push_back(path);这样没问题也有人把判断放在for循环里每选一个元素就判断一次这样会导致单元素结果混入要注意区分。4.5 一份可复用的本地测试小脚本我刷题时会习惯在本地跑这几个用例基本能覆盖所有常见错误输入: [4,6,7,7] 期望: 8 个子序列 输入: [1,1,1,1] 期望: 所有长度 2 且不重复的子序列共 10 个 输入: [1] 期望: 空因为没有任何长度 2 的子序列 输入: [5,4,3,2,1] 期望: 空因为全序列严格递减 输入: [1,2,1,1] 期望: 重点关注是否出现 [1,1] 和 [1,2]且没有乱序结果特别是[1,1,1,1]这个用例一旦你的去重逻辑写错输出数量立刻不对。原数组里长度至少为 2 的子序列本身有很多但由于值全部相同去重之后能用来区分的只有长度所以数量应该是固定可数的。5. 从 491 横向延伸一类高频的回溯去重题5.1 四道经典题目的对照491 不是孤立的把它和子集、排列类题目放在一起对比你会发现回溯去重有一套清晰的方法论。题目保持原顺序是否可排序去重去重位置考核要点78. 子集不要求可排序无需去重模板题90. 子集 II不要求可以排序同层相邻去重排序是前提491. 非递减子序列必须保持不可以排序同层值集合去重去重不能破坏顺序47. 全排列 II不适用可先排序used 标记索引 同层相邻去重排列要区分索引位置从表格可以看到491 的特殊性在于“不能排序”这个约束导致它必须用值集合去重。如果你把这一题弄明白了再去写 90 会容易很多因为 90 的去重是在“排序过”的前提下做的本质是子集问题的扩展。5.2 同层去重和全局去重的语义差异很多人在学回溯时会把所有“去重数组”都叫做used但语义完全不同。在 491 里我们的used是一个只属于本层递归的集合作用域是同一个for循环关键字是“同一层内不重复选择相同值”。而在 47. 全排列 II 这类题里used[i]标记的是某个索引位置的元素在当前递归路径上是否被使用过作用域是整条从根到当前的路径关键字是“同一个元素不能在当前路径中重复使用”。理解这层差异很重要。因为前者用的是“值”维度后者用的是“位置”维度。491 里的第二个7可以在同一个路径的不同层级反复出现只要它们位于不同索引而全排列里的一个索引位置无论在哪个层级都只能使用一次。如果混淆这两个维度代码基本必挂。5.3 这道题在面试和周赛中的价值从 Leetcode 热门 100 题的刷题节奏来看回溯算法本身就是高频考点而 491 恰好把回溯的模板、同层去重、顺序约束三个点合成一题来考非常适合用来判断一个人的算法基本功是否扎实。周赛里也经常能看到类似的思路迁移比如给出一个数组按要求枚举一些保持原顺序的子序列或子集然后去重。通用解法基本就是这套 DFS用startIndex保证顺序用每层局部used保证同值不重复用path做回溯。你在 491 里练熟这套组合拳再遇到周赛里的同类变体题基本上只需要改掉非递减判断条件其他结构都能直接复用。最后分享两个我在复盘时注意到的小细节如果你刚做完这道题建议把[4,6,7,7]的递归树完整画一遍重点关注第二个7在哪些层被允许使用、在哪些层被拦截。画过一遍之后你对“局部去重”的理解会比看十篇题解都深刻。另一个小习惯是提交代码前先用[1,1,1,1]跑一遍这个用例能同时检测出“非递减写错”和“去重范围错误”两类问题我后来做所有回溯题都会先跑这个极值用例。刷题这件事没有捷径但这类题目做透之后去重逻辑在你脑子里会变成一副清晰的图景不再需要靠背模板硬套。