刷到LeetCode 90题的人，绝大多数是刚把78题“子集”写利索，顺手点进下一题，结果发现题目名字就多了个罗马数字II，思路却卡住了。这道题在力扣上的标签非常明确：回溯算法、数组、排序。全网题解都叫它“子集II”，但真正难住人的不是回溯框架，而是“如何去重”——更准确地说，是“为什么排序之后加一个 if 就能去重”。如果你也在这个 if 上犹豫过，这篇文章就用来彻底讲透它。
我会从78题和90题的差异聊起，把递归树画明白，给出可以直接跑的Python和Java代码，再把热词里提到的状压DP枚举子集、第k大子集和这两个延伸点也带一嘴。刷题不是背模版，搞清楚去重逻辑的来龙去脉，你才能在其他回溯题里举一反三。
1. 先看清题：90题和78题的差距只在“去重”两个字
1.1 题目到底要求什么
先把题目翻译成一句大白话：给你一个可能包含重复元素的数组，比如nums = [1, 2, 2]，请你返回所有不重复的子集。注意“可能包含重复元素”这七个字，就是整道题的题眼。
期望输出长这样：
[[], [1], [1,2], [1,2,2], [2], [2,2]]很多人一开始写出来的结果长这样：
[[], [1], [2], [2], [1,2], [1,2], [2,2], [1,2,2]]多了重复的[2]、[1,2]，甚至某些用例下还会出现重复的[2,2]。原因很简单：数组里有两个“2”，它们在数组中的下标不同，但对“子集”来说，{第一个2}和{第二个2}是同一个集合。
这道题的数据范围是1 <= nums.length <= 10，-10 <= nums[i] <= 10。数据量很小，意味着你完全可以用指数级的枚举去做，这也决定了回溯法是标准解法。但指数级枚举如果不去重，输出大小可能接近2^n的重复膨胀，所以题目真正考察的是：在枚举所有子集的过程中，如何把重复分支剪掉。
1.2 为什么直接抄78题会出错
78题“子集”的经典模板长这样：
def subsets(nums): res = [] def dfs(start, path): res.append(path[:]) for i in range(start, len(nums)): path.append(nums[i]) dfs(i + 1, path) path.pop() dfs(0, []) return res这个模板的逻辑非常干净：每次进入递归时，把当前路径“快照”加入结果，然后从start开始尝试每一个元素，选它、递归、回溯。因为题目保证数组元素不重复，所以不需要任何去重。
但把同一个模板套到[1, 2, 2]上，出现重复的根源就很清晰了：两个2的数值一样，但它们在递归树里是两个不同的分支节点。比如外层递归先选择了下标1的2，生成[2]和后续的[2,2]；而递归到某一层时，选择下标2的2作为起点，又会生成一次[2]、一次[1,2]。这些集合在位置上来自不同下标，在集合意义上是同一个结果。
解决办法的第一步是排序。把[2, 1, 2]这类乱序数组排成[1, 2, 2]，让相等的元素变成“相邻元素”。这样一来，所有重复都发生在相邻位置上，我们只需要在同一个递归层的 for 循环里检查nums[i] == nums[i-1]，就能发现“这个值前面已经处理过了”。不排序当然也可以用哈希集合去重，但那是用额外空间换代码简洁，面试时大概率会被追问“能不能不用set”，所以排序才是这条题解路线的地基。
| 对比项 | 78题 子集 | 90题 子集II |
|---|---|---|
| 输入是否有重复元素 | 无重复 | 可能有重复 |
| 核心模板 | 78题回溯模板直接用 | 78题模板 + 排序 + 同层跳过 |
| 去重方式 | 不需要 | 排序后相邻相等跳过 |
| 输出要求 | 返回全部子集 | 子集集合不重复 |
| 复杂度 | O(2^n * n) | O(2^n * n)，常数稍小 |
2. 回溯的“树层”去重：为什么这个 if 是灵魂
2.1 递归树视角看重复来源
想要真正理解90题的去重，最好的方法是在纸上画一棵递归树。拿[1, 2, 2]举例，先排序，然后从空集开始递归：
- 第一层有三个可选下标：0(1)、1(2)、2(2)。选择下标0，整棵子树会长出
[1]、[1,2]、[1,2,2]。 - 第一层选择下标1，子树会长出
[2]、[2,2]。 - 第一层选择下标2，子树也会长出
[2]，但由于前一步已经把下标1的2选过了，这个[2]和上一个[2]撞车了。
问题就出在“第一层已经处理过数值为2的分支”这一点上。第一层选择下标1时，它把“以2开头的所有子集”都生成完了；再选下标2，只是在重复生成同样的集合。
因此去重规则可以概括成一句话：在同一层递归中，如果当前元素和前一个元素相等，并且前一个元素已经被当前层作为起点处理过，那么当前元素直接跳过。这正是网上那句著名的“同层去重，不跨层去重”。
2.2 同层去重写法的关键 if
核心代码非常短，但每个细节都值得拆开讲：
for i in range(start, len(nums)): if i > start and nums[i] == nums[i - 1]: continue path.append(nums[i]) dfs(i + 1, path) path.pop()第一眼看上去，i > start这个条件容易让人犯嘀咕：为什么不是i > 0？为什么不是if nums[i] == nums[i-1]直接跳过？
关键在于start代表什么。start是本层递归可以选择元素的最小下标，也就是说，这一层能选的只有nums[start:]这一段。i > start意味着“当前下标不是本层的第一个可选项”，前面已经有一个相同值的元素被本层尝试过了。而这个“前面相同元素”的所有分支都已经递归完，结果都进了res，所以当前元素再进来注定重复。
那i == start的情况呢？此时即使nums[start] == nums[start - 1]，这个判断也不会触发。举个具体例子：在某个递归层，start = 1，nums[0] = 2，nums[1] = 2。本层第一个可选项是下标1的2，此时该选它，因为它是“当前这一层第一次接触这个数值”，而不是重复处理。真正要去掉的是本层的第二个相同值，也就是i = 2时的情况。这就是i > start而不是i > 0的原因。
注意：这个去重只在“当前递归层内”生效，不去影响不同递归层之间相同值的选用。比如
[1,2,2]中，你可以放心地在选了第一个2之后，再进入下一层递归选择第二个2，最终得到合法的[2,2]。因为那是沿着树的一个分支往下走，不是在同一层重复。
2.3 另一种“选/不选”视角的递归写法
除了从start开始 for 循环枚举，回溯还有一种经典写法：每个元素要么“选”，要么“不选”。90题用这个视角写，同样能去重，但去重条件会更绕，容易把人绕晕。
def subsetsWithDup(nums): nums.sort() res = [] def dfs(i, path, prev_selected): if i == len(nums): res.append(path[:]) return # 选当前元素 if not (i > 0 and nums[i] == nums[i - 1] and not prev_selected): path.append(nums[i]) dfs(i + 1, path, True) path.pop() # 不选当前元素 dfs(i + 1, path, False) dfs(0, [], False) return res这个版本的去重逻辑是：如果是重复元素，并且前一个相同元素刚刚被“放弃”了，那当前这个也不能选，否则会构造出和之前的“不选前一个、选当前一个”完全一样的集合。相比之下，还是start版一眼能看明白。我建议你以start版本为主记忆，选/不选版本了解即可，不需要把两个都当成常用写法。
3. 完整可跑的代码：Python与Java实现
3.1 Python实现
直接给一版适合背诵和默写的代码：
class Solution: def subsetsWithDup(self, nums): res = [] nums.sort() def dfs(start, path): res.append(path[:]) for i in range(start, len(nums)): if i > start and nums[i] == nums[i - 1]: continue path.append(nums[i]) dfs(i + 1, path) path.pop() dfs(0, []) return res每行都值得说清楚：
nums.sort()必须在最前面。它保证了重复元素相邻，后续的nums[i] == nums[i-1]判断才有意义。res.append(path[:])用的是切片拷贝而不是path本身。回溯时path会被持续修改，如果不拷贝，结果里的所有 path 最终都会指向同一个空列表。dfs(i + 1, path)传入的是i + 1而不是start + 1，保证每个元素只能在本分支内被使用一次，避免回头选已经用过的元素。- 去重
if必须在continue之后、加入path之前。顺序反了会导致把重复元素加进路径再回溯，结果反而多了重复子集。
试着用nums = [1, 1, 1]跑一遍，输出应该是：
[[], [1], [1, 1], [1, 1, 1]]只有4个集合，一个不多一个不少。这个极端用例最能检验去重逻辑是否正确。
3.2 Java实现
力扣上Java版本同样高频出现，这里给出完整实现：
class Solution { public List<List<Integer>> subsetsWithDup(int[] nums) { Arrays.sort(nums); List<List<Integer>> res = new ArrayList<>(); dfs(nums, 0, new ArrayList<>(), res); return res; } private void dfs(int[] nums, int start, List<Integer> path, List<List<Integer>> res) { res.add(new ArrayList<>(path)); for (int i = start; i < nums.length; i++) { if (i > start && nums[i] == nums[i - 1]) continue; path.add(nums[i]); dfs(nums, i + 1, path, res); path.remove(path.size() - 1); } } }Java版本里最容易踩的坑是path.remove(path.size() - 1)。如果你不小心写成了path.remove(i)，在 i 已经不再等于末尾下标的情况下，会删错元素，甚至触发IndexOutOfBoundsException。回溯的标准做法永远是删除刚加入的最后一个元素。
3.3 复杂度与边界用例验证
时间复杂度方面，递归过程会生成所有不重复子集，每个子集在加入结果时都要拷贝一次路径，所以整体是O(2^n * n)。这里的n是数组长度，排序的O(n log n)可以忽略不计。空间复杂度主要是递归栈深度O(n)，加上结果集本身占用的O(2^n * n)空间。
边界用例建议顺手测一遍：
[1]：输出[[], [1]]。[1, 2, 3]：无重复元素，应该和78题输出完全一致。[1, 1]：输出[[], [1], [1, 1]]，而不是4个集合。[]：题目虽然没说空数组，但LeetCode官方用例里会出现，输出应该是[[]]。
多测几个极端输入，比背十遍代码都管用。
4. 思考延伸：状压DP枚举子集与第k大子集和
4.1 二进制枚举子集的基本姿势
聊到“子集”两个字，很多老玩家脑海里会同时弹出另一种思路：状态压缩。用二进制位数表示元素选/不选，比如n = 3时，mask = 101表示选第0个和第2个元素。枚举所有mask从0到(1 << n) - 1，就能获得所有子集。
如果拿二进制枚举来写90题，最朴素的做法是把结果放进set去重：
def subsetsWithDup(nums): nums.sort() n = len(nums) res = set() for mask in range(1 << n): cur = [] for i in range(n): if mask >> i & 1: cur.append(nums[i]) res.add(tuple(cur)) return [list(x) for x in res]这个方案能过，但有一个明显缺点：很多mask虽然二进制表示不同，生成的子集却相同。比如[1, 2, 2]中，选下标0和下标1，与选下标0和下标2，得到的[1, 2]是同一个集合。set兜底去重虽然正确，却在一定程度上浪费了枚举次数，而且面试官多半会追问“能不能不用set”。所以二进制枚举更适合用来理解“子集和二进制状态的一一对应关系”，而不是90题的标准答案。
4.2 什么时候用回溯，什么时候用状压
这是我在刷题社区里经常被问到的问题。判断依据其实很直接：看题目要的是“枚举全部集合”还是“在全部集合里做最优/计数决策”。
回溯更擅长“生成”。比如这道题，你需要在递归过程中把每个路径都保存下来，回溯天然合适。它还能配合剪枝提前终止，比如某些分支后续无论怎么选都会超限，就可以在递归入口判断并返回。
状压DP更擅长“决策”。比如“求所有子集的和等于target的方案数”“带容量限制的最大子集和”“子集异或和等于某个值的计数”等问题。这类题目中，状态dp[mask]往往表示“当前选择集合mask时的某种值”，转移也依赖mask的子集枚举。典型场景是n <= 20左右，因为2^20大约100万，勉强可以接受；一旦n到40，直接枚举就爆，需要折半搜索甚至更复杂的优化。
| 维度 | 回溯 | 状压DP |
|---|---|---|
| 适用规模 | n 一般 15 以内，剪枝后可更大 | n 一般 20 左右，配合折半可到40 |
| 输出形式 | 直接得到所有解路径 | 通常只得到最优值或个数，需要额外回溯路径 |
| 去重控制 | 排序 + 剪枝，代码直观 | 靠哈希或预处理，稍绕 |
| 典型题目 | 子集II、组合总和II、分割回文串 | 子集和计数、背包型状态DP、第k大子集和 |
4.3 第k大子集和问题简介
热词里出现的“第k大子集和”是个很好的进阶题，思路也很有意思。它不再是“枚举所有子集”，而是“在所有子集和里找第k大的那一个”。直接全量枚举的成本太高，业界常用的套路是折半搜索。把数组拆成两半，分别枚举所有子集和，得到两个长度约2^(n/2)的列表，再排序。随后用二分答案或优先队列合并这两个有序列表，找出第k大的和。这种做法能把规模从n=20左右推到n=40左右，是面试中的加分技巧。
不过这只是思路延伸，90题本身还是老老实实回溯更稳。它的意义在于提醒你：子集问题的解法不止一种，遇到“如果子集还要满足额外约束”的变形，回溯、状压DP、折半搜索都是工具箱里的备选方案。
5. 实战避坑与我的经验总结
5.1 什么时候用 startIndex，什么时候用 used 数组
很多人在刷完90题之后，紧接着刷47题“全排列II”，会发现去重写法突然变了，多了一个bool[] used。这两个题目的去重差异，其实是所有回溯去重题的公共难点。
判据可以浓缩成这样：如果递归参数带startIndex，说明每一层只会往后看，同一个元素绝不会在同一条路径上被重复使用，此时去重只要做“同层相邻重复跳过”。如果递归参数不带startIndex，比如排列题，元素在每层都可能被重复选，就必须用一张used表标记路径上哪些元素已经用过，同时去重时还要区分“是当前树层上重复还是树支上重复”。
具体到90题，用带startIndex的写法即可，不需要任何额外数组。这种写法在组合总和II（40题）里同样适用，因为组合也只看后面的元素。而47题排列II就必须用used数组。把它们放在一起对比着刷，比单刷十道散题效率高得多。
5.2 面试时如何把去重讲清楚
如果面试官让你现场写90题，写完大概率会问一句：“你这个去重为什么放在i > start的时候？”不要光说“避免重复”，要按这个节奏答：
- 先排序，让相等元素相邻。
- 在一个递归层的 for 循环里，
i每往前走一步，就代表“以nums[i]作为当前层起点”的一个分支。 - 如果
nums[i] == nums[i-1]，说明nums[i-1]已经作为本层某个分支起点，把所有后续子集都生成过了，当前分支只是重复。 - 但
i == start时是本层第一个可选元素，不应该被跳过，所以要判断i > start。
回答完这个“为什么”，这道题基本就稳了。很多面试官特别喜欢追问i > start的边界含义，就是因为这里最能看出一个人到底理解回溯树，还是在背题解。
5.3 我刷这道题留下的几个习惯
最后分享几个个人刷题习惯，算是踩过坑之后总结出来的。
第一个习惯是“排序放在主函数入口，不放在递归函数里”。有一次我图省事，把nums.sort()写进了dfs开头，结果每一层递归都在重复排序，白白增加了很多不必要的O(n log n)开销。排序只需要在真正开始搜索之前做一次，递归里只用下标访问。
第二个习惯是“每个递归分支都要拷贝路径快照”。res.append(path[:])如果哪天被我改写成res.append(path)，整道题的结果就会变成一堆空列表。这种错误在LeetCode上不报错，只在运行结果里悄悄出现，排查起来非常费劲。
第三个习惯是画递归树。刷90题之前先画[1, 2, 2]的递归树，用斜线划掉“同一层第二个2”的分支，再回到代码看那个 if，理解立刻清晰。不要嫌画图浪费时间，实际排查重复子集的效率，比干瞪眼调代码高太多了。
再补充一个小技巧：如果嫌nums[i] == nums[i-1]的写法在C++或Java里看着不够直观，可以写成nums[i] == nums[i - 1]加上一行注释，标明这是“同层去重”。注释的作用是给三个月后的自己看的，别小看这行字。
这道题做好之后，我强烈建议你立刻去刷40题组合总和II和47题全排列II。你会发现它们的去重逻辑几乎一模一样，区别只是递归终止条件和传参方式。把一个“不重子集去重”彻底吃透，整个回溯去重体系就打通了一半。
