刷到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 1nums[0] 2nums[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 ListListInteger subsetsWithDup(int[] nums) { Arrays.sort(nums); ListListInteger res new ArrayList(); dfs(nums, 0, new ArrayList(), res); return res; } private void dfs(int[] nums, int start, ListInteger path, ListListInteger 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大的和。这种做法能把规模从n20左右推到n40左右是面试中的加分技巧。不过这只是思路延伸90题本身还是老老实实回溯更稳。它的意义在于提醒你子集问题的解法不止一种遇到“如果子集还要满足额外约束”的变形回溯、状压DP、折半搜索都是工具箱里的备选方案。5. 实战避坑与我的经验总结5.1 什么时候用 startIndex什么时候用 used 数组很多人在刷完90题之后紧接着刷47题“全排列II”会发现去重写法突然变了多了一个bool[] used。这两个题目的去重差异其实是所有回溯去重题的公共难点。判据可以浓缩成这样如果递归参数带startIndex说明每一层只会往后看同一个元素绝不会在同一条路径上被重复使用此时去重只要做“同层相邻重复跳过”。如果递归参数不带startIndex比如排列题元素在每层都可能被重复选就必须用一张used表标记路径上哪些元素已经用过同时去重时还要区分“是当前树层上重复还是树支上重复”。具体到90题用带startIndex的写法即可不需要任何额外数组。这种写法在组合总和II40题里同样适用因为组合也只看后面的元素。而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。你会发现它们的去重逻辑几乎一模一样区别只是递归终止条件和传参方式。把一个“不重子集去重”彻底吃透整个回溯去重体系就打通了一半。