1. 为什么"子集II"比"子集"难了一个量级：重复元素制造的幻觉

先说结论：LeetCode 90. 子集II这道题，本质上就是在经典的78. 子集（Subsets）上多加了一个条件——数组里可能有重复元素，输出里不能有重复子集。很多人第一次做这道题的时候都会觉得："不就去个重吗，我先把结果全部生成出来，最后用set去重不就行了？"理论上确实可以，实测也会被卡得非常难受。

先讲清楚题目的输入输出长什么样。假设给你nums = [1, 2, 2]，那么正确答案是：

[[], [1], [1,2], [1,2,2], [2], [2,2]]

注意[1, 2]只能出现一次。虽然数组里有两个2，但[1, 2]这个子集只要一个。如果你按照78题的思路直接回溯，会得到[[], [1], [1,2], [1,2,2], [1,2], [2], [2,2], [2]]这种带重复的结果。问题就出在最朴素的回溯没有处理"相同值在同一层递归中被重复选取"这个细节。

这道题在LeetCode上的编号虽然叫"90"，但它其实是回溯专题里的分水岭。78题纯粹是入门模板题，会套框架就能写；40题组合总和II和90题子集II都考同一个去重逻辑；到了491题递增子序列，又把去重换了一种考法。所以90题如果你愿意花一个小时彻底弄懂，等于同时把40题、491题的底子也打了一半。反过来，如果只是背代码糊弄过去，后面碰到"相邻重复""树层去重"这些词照样懵。

另外说一句题外话：算法题不是刷得越多越好，像90题这种"一类题目"的枢纽节点，值得反复做三五遍。我自己的习惯是第一遍看题解抄一遍，第二遍合上书自己推递归树，第三遍不看任何提示默写，第四遍隔一周再回来做，看能不能在十五分钟内AC。每一遍的收获都完全不同，第一遍理解框架，第二遍理解去重边界，第三遍才真正内化成自己的东西。

这道题适合谁？如果你正准备算法面试，它是一道很典型的"中频题"，面试官不会直接拿来当压轴题，但会把它作为回溯的第二问来追问去重细节；如果你在系统学算法，它是理解"树层去重""树枝去重"最直观的样本；就算你只是刷着玩，把这道题吃透后，回头再做78、40、216这些题，会有一种打通任督二脉的清爽感。

2. 回溯的第一步不是写代码，而是先画递归选择树

我见过太多人一上来就写代码，结果卡在去重那里，改来改去把自己绕晕。正确的做法是先画选择树，把"重复从哪来"看清楚。

2.1 从[1,2,2]的选择树看重复如何产生

对于子集问题，每个元素都有两个终极命运：选进当前子集，或者不选。用78题的经典写法，第一层递归会逐个枚举起点：

第一层：选1作为起点 第二层：从2开始 第三层：从第二个2开始 -> [1,2,2] 不选第二个2 -> [1,2] 不选第一个2 -> [1] 第一层：选第一个2作为起点 第二层：从第二个2开始 -> [2,2] 不选第二个2 -> [2] 第一层：选第二个2作为起点（注意，这里就是重复的根源） 不选之后的元素 -> [2]

看出来没有？选第一个2作为起点和不选第一个2、直接选第二个2作为起点，最后得到的[2]完全一样。原因很简单：两个2都是数值2，你在数组里拿的是哪一个2，这个信息对于结果来说毫无意义。回溯搜索的是元素的下标组合，而题目要求的是数值集合，下标不同但数值相同的组合，自然就重复了。

还有一个非常隐蔽的重复：先选下标1的2、再选下标2的2，得到[2,2]；先选下标2的2、再选下标1的2，也得到[2,2]。但因为我们是按顺序枚举起点的，只要递归是从左往右走的，后一种情况永远不会发生。真正要防的是"同一层递归、同一个数值、不同下标"之间的互相替代。

2.2 树层去重 vs 树枝去重：两个容易混淆的概念

这个点是我在群里答疑时被问得最多的。去重到底去的是哪一层的重？

• 树枝去重：沿着一条递归路径往下走，同一个位置上的元素重复使用。比如[1,1,1]这种数组，你可以在一条路径上连续选两个1，这是允许的，因为数组里确实有多个值为1的元素。
• 树层去重：在递归树的同一层上，如果前面已经用某个数值开过头了，后面再遇到同样的数值，继续用它开头只会生成一模一样的子树，必须跳过。

子集II的去重属于典型的树层去重。以[1,2,2]为例，第一层枚举起点时，下标1的2和下标2的2属于同一层，前者已经以2为起点生成过[2]和[2,2]了，后者如果继续走，生成的东西完全相同。所以我们的全部精力都应该花在"如何识别同一层中的重复数值"上。

很多教程会说"先排序，再用if (i > startIndex && nums[i] == nums[i - 1]) continue"，这行代码的精髓在于：排序让所有相等的值相邻排列，nums[i] == nums[i - 1]就意味着"我在这一层上已经处理过这个数值了"。不排序就得用额外的哈希表记录本层已经用过的值，麻烦不少。所以排序是这道题的第一个关键前置动作。

这里有个反直觉的点：排序不是为了输出有序，而是为了去重。排序本身不改变子集的内容，但让重复元素相邻后，"跳过重复"变成一个O(1)的判断。没有排序的时候，你只能每一层开一个长度为n的布尔数组或者哈希集合来标记，空间开销直接翻倍。

2.3 为什么"全部生成再set去重"不是好方案

网上有一种偷懒解法：递归全部结果，最后set(tuple(sub) for sub in result)去重。这个方法在小规模数据上确实能AC，但代价非常明显。

假设数组长度为n，子集总数是2^n，其中重复的子集可能占很大比例。全部生成意味着你依然走了重复的递归路径，时间上是2^n而不是理论上限，空间上更是要先把这堆重复结果全部存下来再筛。以n=20为例，如果全是不重复元素，结果集有约100万个子集，内存勉强撑住；如果有一半重复，最终答案可能只有30万个，但你白白生成了100万个再丢掉70万个，纯属浪费。

更关键的是面试表现。面试官追问"你这里为什么要排序""set去重的时间复杂度是多少"的时候，如果你说"反正最后set一下"，基本等于告诉对方你没理解回溯。面试考算法题从来不是看AC，而是看你能不能把复杂度算明白、把边界说清楚。用set去重的时间复杂度是O(2^n * n)，排序后树层去重是O(n * 2^n)，看着量级一样，但常数差很多，而且后者根本不产生重复子集，内存占用是实打实的答案规模。

3. 核心代码实现：排序 + 回溯 + 同层跳过

3.1 Python写法：最推荐背下来的版本

先给出一版我目前最推荐的写法，它是用startIndex控制搜索范围、用排序保证重复值相邻、用一行判断完成树层去重的标准模板：

class Solution: def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: nums.sort() res = [] path = [] def backtrack(start: int): res.append(path[:]) for i in range(start, len(nums)): # 树层去重：跳过同一层已经用过的重复数值 if i > start and nums[i] == nums[i - 1]: continue path.append(nums[i]) backtrack(i + 1) path.pop() backtrack(0) return res

这套代码只有十几行，核心逻辑就三块：res.append(path[:])负责收集当前路径，for i in range(start, len(nums))负责横向扩展，if i > start and nums[i] == nums[i - 1]负责砍掉重复分支。

展开说一下。为什么收集子集的时机在循环之前？因为path的每一个状态都是一个合法子集，空集也好、长度为2的也好，只要递归进入这个函数，当前的path就是一个答案。把res.append(path[:])放在循环外，保证空集和所有前缀路径都被记录，这是子集问题的固定套路。path[:]是拷贝，如果你直接append(path)，后面pop会把已经存进去的结果改得一塌糊涂。

为什么判断条件是i > start而不是i > 0？这是新手最容易栽的地方。i > 0会把树枝上的重复也卡掉。比如nums = [1, 1, 2]，递归到start = 1时，i = 1，此时nums[1] == nums[0]，但这是同一根树枝上第一次选这个1，应该允许。而i > start的意思是：只有当i不是本层的第一个位置时，才去检查它和前一个值是否相同。前一个值如果等于当前值，说明"以这个值开头的分支已经在这层生成过了"，可以直接跳过。这个边界条件值得在草稿纸上推三个例子，把[1,1]、[1,1,2]、[2,2,2]全画一遍。

3.2 Java/C++版本对比：本质没有任何差别

面试时候考Java或C++的同学也不少，逻辑完全一样，只是语法区别：

class Solution { List<List<Integer>> res = new ArrayList<>(); LinkedList<Integer> path = new LinkedList<>(); public List<List<Integer>> subsetsWithDup(int[] nums) { Arrays.sort(nums); backtrack(nums, 0); return res; } private void backtrack(int[] nums, int start) { 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]); backtrack(nums, i + 1); path.removeLast(); } } }

C++的话把LinkedList换成vector，去重判断完全一样。说实话，算法题跨语言迁移的能力很重要，你理解了回溯的模板逻辑，剩下的就是语法层面的搬运。我见过一些人只背一种语言版本，换语言就卡壳，这其实说明没抓住本质。startIndex的意义、path的进栈出栈、收集结果的时机，这些才是跨语言通用的核心骨架。

3.3 不用排序的替代写法：每层用哈希表标记

有些题目（比如491.递增子序列）不能排序，因为排序会破坏题目要求的相对顺序，这时候就要用哈希表本层去重。写法是这样：

class Solution: def subsetsWithDup(self, nums: List[int]) -> List[List[int]]: res = [] path = [] def backtrack(start: int): res.append(path[:]) used_in_level = set() for i in range(start, len(nums)): if nums[i] in used_in_level: continue used_in_level.add(nums[i]) path.append(nums[i]) backtrack(i + 1) path.pop() backtrack(0) return res

注意used_in_level是定义在backtrack函数内部的，每进入一层递归都会创建一个新的集合，这正好对应"只在本层去重"的语义。如果把它定义成全局或者作为参数传递，就会影响整个搜索树的去重范围，结果就错了。

这种写法的时间复杂度理论上和排序写法一样，但常数更大，而且空间上每层多了一个集合。90题是可以排序的，所以优先用排序写法。但我强烈建议两种都写一遍，因为491题考的就是哈希版本的去重思路，你在这里练熟了，后面遇到不能排序的题会非常从容。

4. 实测踩坑记录：四个最常见的错误和排查方法

这部分是我在实际刷题和带人过程中遇到频率最高的错误，每个错误背后都有一个"看起来没毛病但就是不对"的故事。

4.1 错误一：用 i > 0 代替 i > start，把树枝也砍了

症状是输出结果比正确答案少，比如[1, 2, 2]的结果里丢掉了[1, 2, 2]自己，或者[2, 2]消失。原因是i > 0的条件在start = 1时，第一个元素就被和前一个元素比较，而前一个元素可能是和它数值相同的兄弟，但这在树枝上是合法的连续选择。

我自己第一次写的时候就是这里出错的。当时我的判断是"都sort了，相邻相同就去重，这有什么问题"，结果跑测试用例发现子集数量不对，逐层打印才看到递归树被错误剪枝。排查方法很简单：在回溯函数开头加一行print(start, path, i)，看到底是哪一步跳过了不该跳的分支。遇到递归问题，最忌讳脑内debug，日志输出绝对是最快的手段。

4.2 错误二：忘了排序或排错了对象

有同学会问："数组不是已经有序了吗？"不一定。题目只说了"可能包含重复元素"，没说输入是有序的。nums = [2, 1, 2]这种输入，不排序直接跑，你的去重条件是nums[i] == nums[i - 1]，但两个2中间隔了一个1，根本比较不到，重复照样产生。

还有一种错误是排序排的是原数组而递归里用的是下标索引，这倒不会出错，但要注意如果你用remove或del操作数组就会把下标搞乱。子集II的实现不需要在原数组上做删除操作，全靠start控制范围，所以放心排序。

4.3 错误三：res.append(path) 没加拷贝

这个错误极其隐蔽，因为小数据量下有时候碰巧能过。如果你写的是res.append(path)而不是res.append(path[:])，由于path是一个可变对象，后续的pop会同步修改已经加入res的那些列表。最后你会发现结果集里的所有子集都变成了空集或者同一个残缺状态，因为在递归结束、所有pop执行完后，path变回了空列表。

如果你用的语言是Java，对应的问题就是res.add(path)而不是res.add(new ArrayList<>(path))。这个错误调试起来也很有意思，你打印res的时候它看起来是正常的，因为打印时机在递归过程中，但最终返回出去再看就全错了。建议一开始就养成"存结果必拷贝"的习惯。

4.4 错误四：哈希版本把集合定义在函数外面

如果用哈希表去重，但把used_in_level定义在外层，比如作为类的属性或者通过参数传递，那么去重范围就变成"整个搜索树"，而不是"当前层"。后果是[1, 1, 2]里的第二个1会被直接判重，导致[1, 1]这个子集丢失。判断的标准很简单：集合的生命周期必须和当前递归层绑定，进函数创建，出函数销毁。如果你看到代码里把集合定义在backtrack外面，同时还作为参数传下去，那基本可以断定是错的。

排查这类问题的通用思路是：对照递归树，手工模拟一个[1, 1, 2]的完整搜索过程。模拟完三层，错误就无处遁形。千万别偷懒，画三分钟草图省下半小时调试时间。

5. 复杂度分析和面试延伸：从一道题看懂一类题

5.1 时间复杂度和空间复杂度到底怎么算

子集问题的总状态数是不重复子集的数量，最坏情况（数组内元素全不重复）下是2^n。每个状态需要O(n)的时间拷贝到结果集，所以时间复杂度是O(n * 2^n)。加上排序的O(n log n)，最终可以写作O(n * 2^n)。空间复杂度方面，递归栈深度最大为n，path长度不超过n，结果集存储的是答案本身，不计入辅助空间，所以辅助空间是O(n)。用哈希版本的话，每层多一个集合，最差也是O(n)，量级不变但要常数更大。

如果你在面试里被追问"这个2^n是怎么来的"，可以这样回答：每个元素在一条搜索路径上只有选或不选两种决策，决策树的叶子节点就有2^n个，再加上中间节点也是子集，总状态数不超过2^(n+1)。这个推导既清晰又严谨，比死记公式强。

5.2 两大易混点：为什么不能用contains去重，为什么输入不必有序

第一个问题：能不能在递归里用if nums[i] in path来去重？绝对不能。path里存的是数值，path中有一个2不代表这一层不能再选2。[2,2]这个子集本身就要求连续选两个2。你要去重的是"同一层已经以相同数值展开过分支"，而不是"当前路径中是否含该值"。这两者一个管横向，一个管纵向，混为一谈就是低级错误。

第二个问题：输入有序到底意味着什么？意味着我们可以用"比较相邻元素"的方式识别重复。如果题目给的是无序数组且要求相对顺序不被打乱，那就回归哈希版本。90题支持排序，所以最简单。

5.3 和LeetCode 40、78、491的对照：核心逻辑一模一样

我把这四题的关系总结成一张表，方便你在刷题时建立知识网络：

做完90题之后，强烈建议立刻做一遍40题。40题就是在90题的基础上加了两个条件：需要累计和并判断是否等于target，以及由于每个数不可重复使用，递归参数是i + 1而不是i。去重逻辑一分钱都不用改，直接照搬。你如果能在10分钟内把40题写出来，说明90题真的吃透了。

491题则是考察"不能排序时怎么去重"的变体。题目要求子序列递增，因此不能打乱原数组顺序。此时你在每一层递归里开一个set，记录本层已经用过的值，遇到相同值跳过即可。这里有一个小坑：set里记录的是数值而不是下标，因为同一层的数值重复就一定会生成重复序列。这个思路和90题的哈希版本完全一样，所以如果你把90题的哈希版本练熟了，491题就是顺手的事。

5.4 面试官可能追问的三个刁钻问题

第一问："你的去重条件为什么不用HashSet？"答：因为题目允许排序，排序后相邻比较O(1)就能完成，比哈希表省空间省时间，而且逻辑更直观。如果面试官追问"不能排序怎么办"，这时候再写哈希版本，展示你对两种方案的掌握深度。

第二问："如果改成每个元素可以重复选取，代码怎么改？"答：把递归参数从i + 1改成i即可，但要注意题目会变成组合总和（原39题）的变体，循环条件也要调整。这个追问考察的是你对startIndex语义的理解是否到位。

第三问："你能用选/不选的二叉树思路来写吗？"这个问题比较刁钻，因为不排序的话选/不选版本很难做同层去重，所以一般建议回答"用for循环展开的版本更符合子集问题逐层生成的自然语义，也方便去重"。如果你真想挑战，可以用选/不选 + 每层哈希也能实现，但要控制used变量的生命周期，略微绕。扎实掌握主流的for循环版本就足够应对绝大多数考核场景。

6. 实战心得：我刷这道题的完整复盘与建议

最后聊聊我自己的实际操作过程。我第一遍做90题的时候，看了三遍官方题解才看懂那一行i > start && nums[i] == nums[i - 1]，后来干脆在纸上把[1, 2, 2]的递归树全部画出来，用不同颜色的笔标出哪些分支是重复的，这才彻底搞明白。画完之后发现整棵树的规模其实很小，但重复的枝叶占了将近三分之一，这让我第一次直观感受到"树层剪枝"节省的到底是多少计算量。

第二遍我做的是40题，果然顺畅许多，去重逻辑直接照搬，只改了累计和判断。第三遍我做491题，在哈希去重上又栽了一次，后来发现是集合的生命周期搞错了，把集合定义在函数外面导致[1,2,3,1,1]漏解。这三遍做完，我再看到"子集""组合""子序列"这类的回溯题，第一反应就是：有没有重复？能不能排序？同一层如何识别重复？这套思维模板已经固化了。

给你一个建议：刷题时准备一个错题本，不用抄全代码，只记录"题目编号 + 错误原因 + 一句话修正"。比如90题写"忘了排序导致相邻判断失效"，40题写"sum > target时可以提前break但注意要排序后才有单调性"，491题写"哈希集合必须在每层新建"。这些一句话笔记的价值高于任何教程，因为它是你自己的思维漏洞清单。

如果你现在正卡在90题上，别急。先画两个用例的选择树，再看本文第三节的代码，然后把代码默写一遍，最后去跑测试。跑通了再用[1,1,1,1]这种极端用例验证边界。相信我，当你能独立讲清楚"为什么i > start而不是i > 0"的那一刻，你的回溯水平已经提升了不止一个档次。这道题刷透之后，后面遇到再复杂的DFS剪枝题，你都能在十分钟内定位核心思路。