刷LeetCode的人一多半都会卡在回溯上。倒不是递归本身多难而是“剪枝”和“去重”这两个词听起来很玄真正落笔写条件的时候不知道写在哪里、怎么写。LeetCode 90题“子集II”就是最典型的例子它比78题只多了一个“数组中包含重复元素”但通过率比78题低了将近20%。这个差距不是算法难度造成的而是很多人没想明白一个问题——到底要“去”什么“重”。这篇文章我按自己的刷题习惯来写不绕弯子直接讲清楚三件事为什么必须先排序排序之后同层去重怎么写以及常用的 used 数组和排序跳过两种方案怎么选。适合正在刷回溯专题的新手、准备面试想快速复习套路的人也适合教算法时想给学生讲透去重原理的读者。看完之后你不仅能AC这道题还能把子集、组合、排列这三类去重逻辑串起来。1. 题目拆解子集II到底在考什么1.1 子集、子序列、组合的关系先明确一个概念子集和组合在算法题里经常是同一件事。给定一个数组 [1,2,2]它所有不重复的子集是空集 []长度为1的[1]、[2]长度为2的[1,2]、[2,2]长度为3的[1,2,2]为什么没有 [1,2] 出现两次因为两个下标不同的 2 选出来之后得到的集合都是 {1,2}它们该被视作同一个子集。LeetCode 78题“子集”是基础版数组中元素互不相同直接枚举所有组合即可。LeetCode 90题“子集II”的唯一区别就是数组中可能有重复元素所以必须做去重处理。听起来只是加几行判断的事但这几行判断的位置和写法决定了你的代码是 AC 还是 WA。注意一个容易混淆的点子集和子序列不一样。子集不要求保持原数组的相对顺序比如 [2,1] 也可以是 [1,2,3] 的子集只要元素都能在数组里找到。而子序列必须保持相对顺序。LeetCode 90题属于“子集”不要求顺序所以我们完全可以先排序再枚举排序这个操作不会改变结果集合本身只会让重复元素变得相邻。1.2 重复元素为什么让人头疼如果不做任何去重处理直接套用78题的递归框架结果会多出一批重复集合。举个例子nums [1,2,2]递归生成子集时可能走出两条不同的分支分支A选下标0的1再选下标1的2得到 [1,2]分支B选下标0的1再选下标2的2得到 [1,2]两个结果集合完全相同但被统计了两次。原因很简单我们是在“按下标”枚举而不是按“值”枚举。两个不同下标的 2在集合层面是同一个元素。所以去重的本质是当多个下标对应的值相同且它们产生的集合也相同的时候只保留其中一个分支。这个逻辑可以用“排序 相邻判断”来解决也可以用一个布尔数组 used 来标记“之前用过没有”。两种方案的取舍我放到后面细讲。2. 回溯框架先跑通78题再看90题2.1 最朴素的子集写法先说78题的经典递归框架。这个框架几乎所有回溯题都能套维护一个 path 表示当前路径每次递归先记录当前路径为一个结果然后从 startIndex 开始尝试把后面的元素加进 path递归结束后撤销选择。from typing import List class Solution: def subsets(self, nums: List[int]) - List[List[int]]: res [] path [] n len(nums) def dfs(startIndex: int): res.append(path[:]) # 每个节点都代表一个子集 if startIndex n: return for i in range(startIndex, n): path.append(nums[i]) dfs(i 1) path.pop() dfs(0) return res这段代码为什么能枚举出所有子集因为每个子集都可以看作“从某个下标开始选择若干个元素”。递归每深入一层就选一个元素递归返回后就撤销选择试另一个元素。path 在递归树上走的路径就是从空集到某个子集的过程。这里有个特别容易踩的坑res.append(path[:])不能写成res.append(path)。因为 path 是同一个列表对象后面还会被反复修改如果直接 append path最后 res 里保存的全是同一个列表的引用输出结果全是同一个“最终态”。用path[:]相当于复制一份快照。2.2 加了“重复”之后筛选逻辑要改哪里现在把 nums 改成 [1,2,2]如果直接跑 78 题的代码你会发现输出里出现了两个 [1,2] 和两个 [2]。原因刚才说了两个下标不同的 2被当成了两个独立元素。去重的核心思路是在枚举同层元素时如果当前元素和前一个元素相等就跳过当前这个分支。但这里有个关键细节“前一层”和“同一层”的边界要分清楚。什么意思呢看下面这段错误的去重写法for i in range(startIndex, n): if i 0 and nums[i] nums[i - 1]: continue ...这种写法把所有相邻重复值都跳过了。结果就是输入 [1,2,2] 时子集 [1,2,2] 和 [2,2] 会丢失。因为递归到第三层时startIndex2i2此时 nums[2] nums[1]被 continue 掉了而实际上它应该被选中。问题出在它把“同一分支上连续取相同值”的情况也排除掉了。同一个子集内允许出现重复值比如 [2,2] 表示两个 2 同时被选入被禁止的只是“在不同分支上生成重复集合”。所以正确写法要用 i 和 startIndex 的关系来判断i startIndex and nums[i] nums[i - 1]。这个条件的含义是只有当 i 不是本层枚举的第一个元素时才去比较相邻值。本层枚举的第一个元素绝对不可能是“由前一个同值元素重复生成”的因为前一个同值元素根本不在本层范围里。3. 去重的两种实现used数组和排序跳过3.1 排序是去重的前提无论用哪种去重方案第一步都是排序。排序的目的是把相同元素堆到一起这样重复项一定出现在相邻位置判断起来只需看前一个。如果不排序重复值散落各处想要判断“当前值之前是否出现过”代价会变大要么开哈希表要么遍历历史都不如排序干净。很多刚接触的人会问子集不要求顺序排序会不会改变结果不会。因为最终你返回的是集合的列表集合本身不关心元素顺序。排序只影响你枚举元素的顺序不影响集合的内容。这也是为什么这类“数组中有重复元素求所有组合”的题排序几乎成了标准操作。3.2 写法一同层跳过我推荐这个这是我最推荐初学者掌握的写法代码短逻辑直观不用额外数组。class Solution: def subsetsWithDup(self, nums: List[int]) - List[List[int]]: nums.sort() res [] path [] n len(nums) def dfs(startIndex: int): res.append(path[:]) if startIndex n: return for i in range(startIndex, n): if i startIndex and nums[i] nums[i - 1]: continue path.append(nums[i]) dfs(i 1) path.pop() dfs(0) return res关键就一行if i startIndex and nums[i] nums[i-1]。解释一下这个条件背后的逻辑。在 for 循环里i 代表“当前层正在尝试选第几个元素”。如果 i 等于 startIndex说明这是该层第一次尝试即使它和前一个元素值相同那也是因为上一层已经选了前一个位置的值现在要从本层新的起点继续不构成重复分支。举个例子在 dfs(1) 这一层startIndex1进入循环时 i1此时 nums[1]2虽然 nums[1]nums[0]2假设前一个也是2但 i startIndex不能跳过否则 [2,2] 这种合法子集就丢了。而当 i 大于 startIndex说明前面已经有某个同值元素在同一个 for 循环里被处理过了。比如 startIndex0 时i1 选了一个2生成了以 [2] 开头的所有子集i2 又遇到一个2那它生成的所有分支都和 i1 时重叠所以直接 continue。用一句话总结在一条垂直往下的递归路径里相同元素可以重复选在同一层横向循环里相同元素只能选一次。3.3 写法二used数组的“前一个没用过才跳过”另一个常见做法是用 used 数组记录每个下标是否在当前递归路径上。这种写法在排列类题目里更常见但也能处理子集去重。class Solution: def subsetsWithDup(self, nums: List[int]) - List[List[int]]: nums.sort() res [] path [] used [False] * len(nums) n len(nums) def dfs(startIndex: int): res.append(path[:]) if startIndex n: return for i in range(startIndex, n): if i 0 and nums[i] nums[i - 1] and not used[i - 1]: continue used[i] True path.append(nums[i]) dfs(i 1) used[i] False path.pop() dfs(0) return res这里的关键条件是not used[i - 1]。为什么“前一个没用过”才跳过想象一下递归执行到某个状态nums [1,2,2]当前 path [1]正在第二层循环。i2 时发现 nums[2]nums[1]如果此时 used[1] 是 True说明前一个2还在当前递归路径上当前这个2是“往下延伸”的属于合法分支允许选择如果 used[1] 是 False说明前一个2已经被撤销了当前循环是在横向尝试另一个同值元素生成结果一定和之前重复所以跳过。这个逻辑和排序跳过的本质是一样的只是用 used 数组显式记录状态判断起来更直观。缺点是每次递归要维护一个额外数组而且“not used[i-1]”这个条件对初学者来说反直觉经常记反。3.4 两种写法对比对比维度排序 同层跳过排序 used数组核心判断i startIndex and nums[i] nums[i-1]i 0 and nums[i] nums[i-1] and not used[i-1]额外空间无O(n)理解难度中等需要理解 startIndex 的作用较高需要理解 used 的状态含义适用题型子集、组合类排列类如全排列II代码长度短略长我的建议是子集和组合题优先掌握排序同层跳过的写法因为它不依赖额外状态数组写起来快。排列题再学 used 数组方案因为排列没有 startIndex 概念只能靠 used 判断某个位置是否已经被填过。4. 实操过程代码走读与手推 [1,2,2]4.1 完整代码与复杂度把排序同层跳过的完整代码再贴一遍这次加上注释方便直接复制去LeetCode跑。from typing import List class Solution: def subsetsWithDup(self, nums: List[int]) - List[List[int]]: nums.sort() # 1. 排序让重复元素相邻 res [] # 2. 收集所有结果 path [] # 3. 当前路径 n len(nums) def dfs(startIndex: int): res.append(path[:]) # 4. 每次进入递归先记录当前子集 if startIndex n: return for i in range(startIndex, n): # 5. 同一层循环中跳过重复元素的分支 if i startIndex and nums[i] nums[i - 1]: continue path.append(nums[i]) # 6. 选中当前元素 dfs(i 1) # 7. 下一个元素从 i1 开始 path.pop() # 8. 撤销选择回溯 dfs(0) return res时间复杂度子集总数最多是 2^n每次生成子集时需要把 path 拷贝一份加入结果拷贝耗时 O(n)。递归过程中实际访问的节点数小于等于 2^n所以总复杂度 O(n * 2^n)。当然如果结果里元素数组很长最终占用空间也是 O(n * 2^n)这是输出本身的大小省不掉。递归深度最坏 O(n)不考虑结果的话辅助空间是 O(n)。空间复杂度需要注意的点res 用于存储所有结果占用的空间是结果数量乘以每个子集的平均长度硬要算就是 O(n * 2^n)。如果面试官问辅助空间递归栈和 path 只需要 O(n)。4.2 手推一遍递归过程拿 nums [1,2,2] 为例手动走一遍你能直观感受去重发生的位置。排序后 nums [1,2,2]调用 dfs(0)。dfs(0)先记录 []然后进入 for 循环。i0值为1。i startIndex不需要判断去重path[1]调用 dfs(1)。dfs(1)记录 [1]进入 for 循环startIndex1。i1值为2。i startIndex不触发 continuepath[1,2]调用 dfs(2)。dfs(2)记录 [1,2]进入 for 循环startIndex2。i2值为2。i startIndex虽然 nums[2]nums[1]但不跳过。path[1,2,2]调用 dfs(3)。dfs(3)记录 [1,2,2]startIndexnreturn。回到 dfs(2)path 弹出2恢复为 [1,2]。for 循环结束回到 dfs(1)。dfs(1) 中for 循环继续i2值为2。此时 i2 startIndex1且 nums[2]nums[1]触发 continue跳过。这一步去重了重复子集 [1,2]。for 循环结束回到 dfs(0)path 弹出1恢复 []。dfs(0) 中for 循环继续i1值为2。i startIndex0但 nums[1]2 ! nums[0]1不触发 continue。path[2]调用 dfs(2)。dfs(2) 中startIndex2记录 [2]。i2值为2i startIndex不跳过path[2,2]调用 dfs(3)。dfs(3)记录 [2,2]return。回到 dfs(2)path 弹出2循环结束回到 dfs(0)。dfs(0) 中for 循环继续i2值为2。i2 startIndex0且 nums[2]nums[1]触发 continue跳过不再生成以 [2] 开头的重复子集。最终 res [[], [1], [1,2], [1,2,2], [2], [2,2]]正好6个子集没有重复。注意第6步和第12步的去重。第6步去掉的是 [1,2] 的重复第12步去掉的是 [2] 的重复。看起来都是“跳过第二个2”但所在层级不同本质都是“同一层循环里第二个相同值不能作为新的起点”。4.3 常见误区和排查技巧下面这几个问题是我在实际刷题、帮别人 review 代码时见过最多的。误区一去重条件写成if i 0 and nums[i] nums[i-1]这个前面说过了会丢解。具体丢在哪些测试用例上比如 nums[1,2,2][2,2] 和 [1,2,2] 会丢。因为你把递归下沉路径里合法的重复也跳了。改成i startIndex就好。误区二忘记排序如果不排序相邻判断就没有意义。比如 nums[2,1,2,1]重复元素不在一起你无法通过“和左边比”发现重复。这个错误通常表现是提交结果里有重复但 debug 时又觉得逻辑没问题。先排序再看去重。误区三把path[:]写成path表现是输出结果里每个元素都一样或者结果数量对但内容全错。原因是 list 是引用类型回溯时会原地修改 pathres 里存的引用同一地址。直接复制列表path[:]或path.copy()都能解决。误区四在 res.append 之前进行去重判断有时候有人把去重写在 append 之前比如“当前 path 已经在 res 里了就不再添加”这样虽然能去掉重复结果但会让代码变得很慢。因为每次都要遍历 res 比较整个 path复杂度直接翻倍。去重应该在枚举分支时就做掉而不是等结果生成后再过滤。误区五用了 used 数组但忘了在 pop 之后恢复 used[i] Falseused 数组方案在回溯过程中必须成对出现选中的时候置 True撤销的时候置 False。一旦忘记恢复状态就会污染后续分支导致大量错误结果。即使你写的逻辑是对的只要漏了这行debug 会很痛苦。5. 从90题延伸开去5.1 组合、排列的去重思路差异子集II的去重逻辑不是孤立的。LeetCode 40题“组合总和II”和它几乎一个套路只是多了一个目标和限制同样需要排序后同层去重。LeetCode 47题“全排列II”则是另一种框架因为排列需要枚举所有位置的组合没有 startIndex 限制所以必须用 used 数组去重。做个对比表帮你理解不同题型的模板差异题目枚举方式去重方案核心条件78 子集递归枚举下标不需要无90 子集II递归枚举下标同层跳过i startIndex40 组合总和II递归枚举下标同层跳过i startIndex47 全排列II递归枚举位置used数组not used[i-1]可以看到子集和组合题天然适合用 startIndex 控制枚举起点去重也顺势用 startIndex 判断排列题需要遍历所有位置就转用 used 数组。面试时如果能讲清这个区别比单纯 AC 一道题加分很多。5.2 位运算解法与额外空间除了递归回溯子集类题目还有一种常见解法是用位运算枚举所有子集。因为每个位置有“选”和“不选”两种状态n 个元素就有 2^n 个子集正好对应 0 到 2^n - 1 的所有二进制表示。class Solution: def subsetsWithDup(self, nums: List[int]) - List[List[int]]: nums.sort() res [] n len(nums) for mask in range(1 n): path [] duplicate False for i in range(n): if mask (1 i): if i 0 and nums[i] nums[i - 1] and (mask (1 (i - 1))) 0: duplicate True break path.append(nums[i]) if not duplicate: res.append(path) return res这里去重的判断思路是如果当前二进制位选了第 i 个元素但第 i-1 个同值元素没被选中说明当前这个选择方案一定能用“选第 i-1 个、不选第 i 个”的某个更早方案替代属于重复所以跳过。这种写法不需要递归但需要理解二进制枚举细节比回溯更多。我实际用下来觉得位运算适合笔试时快速提交不适合面试时讲思路。面试官更希望听到“排序 回溯 去重”这种分步清晰的解法。5.3 面试时怎么讲让面试官觉得你真懂了如果你在面试中遇到这道题别急着甩代码。我建议按这个顺序讲第一句子集问题可以用回溯枚举所有组合模板是先排序再用 startIndex 控制不回头。 第二句这题多了重复元素所以在 for 循环的同一层里如果当前值和前一个值相同就跳过因为前一个值已经枚举过从这个值开头的所有组合。 第三句注意去重条件要写成 i startIndex不能写成 i 0否则会丢掉 [2,2] 这种包含重复元素的合法子集。 第四句复杂度是 O(n * 2^n)空间是 O(n)不计输出。如果面试官追问“为什么排序不会影响子集结果”你就说子集只关心集合内容不关心顺序排序只改变枚举顺序集合本身不变。这句话很多人答不好但只要理解到位一句话就能说清。我的一点刷题体会这题我前前后后刷了三遍每次重新写还是会想起最早踩过的坑。回头看90题其实只考一个点你有没有分清“同层重复”和“同路径重复”。只要把这个点想透排序同层跳过就是手到擒来。最后分享一个判断技巧看到“数组里有重复元素 求所有子集/组合/排列”这组特征第一反应就是先排序然后在循环条件里处理去重。至于是用 i startIndex 还是 used 数组取决于题目是子集/组合还是排列。多画两次递归树这个判断就能形成肌肉记忆。回溯这种东西光看是真看不明白的拿笔在纸上推一遍比对着屏幕盯半小时有用得多。