1. 题目拆解与核心考点分析LeetCode 90题“子集II”是经典回溯算法题目同时也是面试中非常高频的一道题。如果你已经刷过LeetCode 78题“子集”那么这道题就是在它基础上增加了一个条件给定数组可能包含重复元素。就是这个“重复”二字让无数人在第一次写代码时踩了坑。先说清楚题目要求给定一个可能包含重复元素的整数数组返回所有可能的子集解集不能包含重复的子集。示例是nums [1,2,2]输出需要是[[], [1], [1,2], [1,2,2], [2], [2,2]]注意不能出现两个[2]也不能出现两个[1,2]。1.1 题目到底在问什么子集问题的本质是对于数组中的每个元素都有“选”和“不选”两种状态穷举所有组合。比如[1,2]你可以选1不选2得到[1]可以选2不选1得到[2]两个都选得到[1,2]两个都不选得到[]。所以[1,2]一共有2^24个子集。到了[1,2,2]理论上应该是2^38种组合但因为有两个2是相同的其中有些组合会被重复计算。比如你选了第一个2没选第二个2和你选了第二个2没选第一个2结果都是[1,2]这在题目看来是同一个子集只能保留一个。这道题和LeetCode 78最大的区别就在这里78题数组元素互不相同暴力穷举不会产生重复90题数组里有重复元素必须想办法去重。1.2 为什么“子集II”让很多人卡住我见过不少同学看题解能看懂轮到自己动笔就经常出错原因主要有两个。第一去重的逻辑容易混淆。很多人会习惯性地想既然最终结果不能有重复子集那我用一个HashSet来存结果重复的就过滤掉这不行吗从结果上看确实能去重但这么做在LeetCode上很容易超时因为生成重复解的过程一个都没少只是最后被过滤掉了。如果是纯求正确答案HashSet确实能过一些测试用例但复杂度高了很多面试时更不是最优解面试官也不会满意。第二回溯模板虽然好背但去重写在哪里、怎么写有很多细节。比如为什么在i startIndex时跳过而不是在i 0时跳过为什么排序是必需步骤这两个问题搞不清楚代码改来改去都是错的。1.3 面试官到底想考察什么从面试的角度看子集II考的是三件事回溯算法的基本框架、去重思路的清晰程度、以及对组合类问题中“重复”问题的理解深度。回溯的基本框架是做选择、递归、撤销选择。这个谁都会背但“去重”才是区分度所在。面试官想听你讲清楚“为什么排序后同层跳过重复元素就能去重”而不是你死记硬背“i startIndex nums[i] nums[i-1]要continue”这段代码。能把背后的树形结构讲明白面试这关基本就稳了。2. 从穷举到去重两种主流解法的思路对比子集II的解法并不唯一主流的写法有两种一是“排序同层去重”的回溯写法二是“used数组标记”的写法。两种思路本质上是一样的代码上略有差异搞清楚它们各自的特点你就能在不同场景下灵活切换。2.1 回溯法标准的“选或不选”模型先回顾一下回溯法的基础模板这个模板几乎适用于所有子集、组合、排列类问题void backtrack(ListInteger path, int startIndex) { result.add(new ArrayList(path)); for (int i startIndex; i nums.length; i) { path.add(nums[i]); backtrack(path, i 1); path.remove(path.size() - 1); } }这段代码的逻辑是先收集当前路径作为一个子集然后依次尝试从startIndex开始往后选元素每次选完就递归递归完撤销选择。用[1,2,2]来走一遍第一层会选1、选2、选第二个2第二层会基于第一层的选择继续往下选。对于[1,2,2]来说如果不做去重第一层选了第一个2和第二个2时下面展开的结果是完全相同的因为两个2本身一样。2.2 排序同层去重核心思路全解析去重的关键在于先把数组排序让重复元素挨在一起然后在同一层循环中跳过已经用过的重复值。为什么排序是必需的因为只有排序之后相同的值才会相邻你才能用“当前元素和前一个元素是否相等”来判断这是不是一个重复的开始。如果不排序[2,1,2]这种输入会让两个2分散在不同位置nums[i] nums[i-1]的判断就完全失效了。接下来是核心中的核心判断条件为什么是i startIndex而不是i 0这里我画个简单的树形结构来解释。想象回溯的过程是一棵多叉树第一层从startIndex0开始会依次选择每个元素作为子集的第一个元素第二层的startIndex是上一层选了元素位置的后一位。i startIndex的含义是当前元素不是这一层循环中第一个被尝试的元素。如果nums[i] nums[i-1]说明当前元素和本层前一个元素的值相同那么以当前元素开头的所有分支一定和以nums[i-1]开头的所有分支产生相同的结果。所以直接跳过这就是“同层去重”。而i 0之所以不能用是因为它把不同层的重复也去掉了。比如[1,2,2]当你已经选了第一个2递归进入下一层时仍需要再选第二个2来得到[2,2]这个子集。如果此时用i 0判断会导致第二个2因为和前一个元素相同而被跳过最终结果就少了[2,2]和[1,2,2]这两个正确子集。为了更容易理解你可以把回溯过程想成一组人排队轮流当队长同一轮排队的人如果和前一个同名就没必要再让他当一次因为结果一样但下一轮新加入的人名字即使和上一轮的人相同也完全可以参与因为队形不一样了。2.3 用used数组的另一种写法除了“同层去重”还有一种常见的写法是引入一个boolean[] used数组标记某个元素是否被使用过。这种写法在LeetCode 47“全排列II”中更常见但用在子集II上也完全没问题。核心判断逻辑是if (i 0 nums[i] nums[i - 1] !used[i - 1]) { continue; }这行代码的含义是如果当前元素和前一个元素相等并且前一个元素还没被使用过说明当前元素走的是和前一个元素同层的分支直接跳过。你可能会问什么时候用used[i - 1]是false在回溯过程中每层递归结束后会把选择撤销所以回到上一层时上一层尝试过的元素会被标记为未使用。此时如果你再遇到一个和前一个元素值相等的新元素说明它和上一个元素处于同一层、同一个位置是重复尝试需要跳过。那如果used[i - 1]是true呢说明前一个元素已经被使用在当前路径中意味着这不是同层重复而是下一层的合法选择。比如[1,2,2]中选了第一个2后递归到下一层此时used[1]true再遇到第二个2时used[1]true所以不会跳过这样就能正确生成[2,2]。两种去重方式的本质是一样的区别只是判断同层的方式不同一个利用i startIndex一个利用used数组的前一个元素状态。面试时你选自己熟悉的写就行但一定要能解释清楚为什么这么写。2.4 位掩码枚举解法除了回溯法子集还有一个“位掩码”解法也算是一种补充思路。对于长度为n的数组共有1 n个子集每个数字的二进制表示为从0到2^n - 1第i位是1就表示选取nums[i]。public ListListInteger subsetsWithDup(int[] nums) { Arrays.sort(nums); ListListInteger result new ArrayList(); int n nums.length; for (int mask 0; mask (1 n); mask) { ListInteger cur new ArrayList(); boolean duplicate false; for (int i 0; i n; i) { if ((mask (1 i)) ! 0) { if (i 0 (mask (1 (i - 1))) 0 nums[i] nums[i - 1]) { duplicate true; break; } cur.add(nums[i]); } } if (!duplicate) { result.add(cur); } } return result; }这段代码里判断重复的逻辑是如果当前要选第i个数但前一个相同的数没有选二进制位为0说明当前这个组合在之前已经出现过了标记为重复。这个思路在LeetCode 90的讨论区也有人写但它只适用于理解用真正面试写代码我还是推荐回溯法因为回溯法更容易讲清楚思路也更容易在后续题目中复用。3. 代码实现与踩坑实录这一部分直接上能跑的代码并且我会尽量把每一步的逻辑都解释清楚包括为什么这样写、有哪些容易忽略的细节。3.1 回溯法完整代码推荐写法class Solution { ListListInteger result new ArrayList(); ListInteger path new ArrayList(); int[] nums; public ListListInteger subsetsWithDup(int[] nums) { Arrays.sort(nums); this.nums nums; backtrack(0); return result; } private void backtrack(int startIndex) { // 每个节点都是一个子集 result.add(new ArrayList(path)); for (int i startIndex; i nums.length; i) { // 同层去重跳过重复元素 if (i startIndex nums[i] nums[i - 1]) { continue; } path.add(nums[i]); backtrack(i 1); path.remove(path.size() - 1); } } }这段代码核心就一个地方i startIndex nums[i] nums[i - 1]。我建议你把它背下来但更重要的是理解它。我逐行说一下执行过程。以nums [1,2,2]为例调用backtrack(0)先把空集[]加入结果。循环i0nums[0]1加入pathpath[1]调用backtrack(1)。在backtrack(1)中先把[1]加入结果然后循环i1nums[1]2path[1,2]调用backtrack(2)。在backtrack(2)中加入[1,2]循环i2nums[2]2path[1,2,2]调用backtrack(3)。backtrack(3)中加入[1,2,2]此时i3循环结束回退到上一步。上一步的循环中i2处理完后i变为3循环结束回退到backtrack(1)。backtrack(1)中继续i2nums[2]2但此时i2 startIndex1且nums[2] nums[1]跳过。这一步就是同层去重的关键。backtrack(1)循环结束回退到backtrack(0)。backtrack(0)中继续i1nums[1]2path[2]调用backtrack(2)。此时startIndex2。backtrack(2)中加入[2]循环i2nums[2]2且i2 startIndex2不i2等于startIndex2所以不去重加入path得到[2,2]递归下一层加入[2,2]。以此类推最终结果就是[[], [1], [1,2], [1,2,2], [2], [2,2]]。走一遍流程你会发现步骤7里去重跳过的是“第一层已经选过2作为第一个元素所以第二层不能重复选2作为第一个元素”而步骤10里不去重是因为第二个2是在第一个2已经被选入路径的情况下作为下一层新增元素加入的结果[2,2]是合法且唯一的。3.2 used数组版本完整代码如果你更习惯used数组的写法参考下面这段class Solution { ListListInteger result new ArrayList(); ListInteger path new ArrayList(); boolean[] used; public ListListInteger subsetsWithDup(int[] nums) { Arrays.sort(nums); used new boolean[nums.length]; backtrack(nums, 0); return result; } private void backtrack(int[] nums, int startIndex) { result.add(new ArrayList(path)); for (int i startIndex; i nums.length; i) { if (i 0 nums[i] nums[i - 1] !used[i - 1]) { continue; } used[i] true; path.add(nums[i]); backtrack(nums, i 1); path.remove(path.size() - 1); used[i] false; } } }这个版本在LeetCode 90上同样能通过。相比第一种写法它多维护了一个used数组在递归前后标记状态。判断条件!used[i - 1]和第一种写法中i startIndex起到了相同的作用判断当前元素是不是同层重复。用[1,2,2]验证一下当backtrack(0)中i1选择了第一个2进入递归前used[1]true递归回来后撤销used[1]false然后i2指向第二个2此时nums[2]nums[1]且used[1]false说明前一个2在同层已经被尝试过了于是跳过。3.3 复杂度分析时间复杂度和空间复杂度这块是面试必问的点一定要能答上来。时间复杂度方面子集问题的解空间大小是O(2^n)也就是说最终结果里最多有2^n个子集。每个子集复制到结果列表时需要O(n)的时间所以总体是O(n * 2^n)。去重只是减少了生成重复结果的时间但最坏情况下元素全部不同仍然是要遍历所有2^n种情况所以复杂度不变。空间复杂度方面递归深度最多为n所以调用栈是O(n)path列表最多装n个元素也是O(n)结果列表result需要存O(2^n)个子集每个子集最长n所以总空间是O(n * 2^n)。如果只算额外空间不算结果空间那就是O(n)。3.4 我踩过的三个坑第一个坑忘记排序。我最初写这道题时拿到[1,2,2]心想数组本来就是有序的直接跳过排序。结果提交后有些用例输出多个重复子集。后来换了[4,4,1,4]这种无序输入才发现问题不排序的情况下重复元素不在相邻位置去重判断根本没法生效。所以记住任何涉及去重的子集/组合题第一件事就是排序。第二个坑把startIndex写成i。递归调用时应该是backtrack(i 1)表示下一层从当前元素的下一个位置开始选。我之前有一次写成了backtrack(startIndex 1)导致递归过程中反复尝试已经用过的元素结果输出了一堆重复组合还出现了[1,1]这种不存在的子集。第三个坑想用HashSet去重。有一阵子我偷懒直接SetListInteger存结果最后再转回List。小用例能通过但遇到数组长度比较大的用例运行时间直接爆表。原因很简单回溯生成重复子集的过程一个不少只是到最后被过滤掉白白浪费了大量时间。在LeetCode上会超时在面试中会被追问“能不能优化”非常尴尬。4. 常见问题排查与相关题目扩展这道题做完之后我建议你把类似的几道题放到一起刷对比它们的异同。这样你会对“去重”这件事有一个体系化的理解而不是每道题都重新碰一遍壁。4.1 面试中常见的追问第一次写这道题时你大概率会关心下面这几个问题也都是面试官喜欢追问的点。问为什么i startIndex而不是i 0答因为startIndex是当前层开始尝试的起点i startIndex说明当前元素不是本层循环的第一个元素。如果它不是第一个且和前一个值相同那么它产生的所有结果都和前一个元素产生的结果重复应该跳过。如果用i 0会把不同层的重复也禁止掉导致漏解。问为什么排序后只需要检查相邻元素答排序后相同的元素会排在一起。只要当前元素和前一个元素不同它和更前面的元素肯定也不同所以只需要比较nums[i]和nums[i - 1]就够了。问这个去重逻辑放到“组合总和II”里还适用吗答适用。LeetCode 40“组合总和II”的子集生成逻辑和这道题几乎一样区别是多了target的剪枝条件以及需要判断当前和是否超过目标值。核心的去重逻辑if (i startIndex nums[i] nums[i - 1])完全一样。4.2 相关题目对比78、40、47LeetCode 78“子集”是这道题的基础版没有重复元素所以不用去重直接回溯即可。代码上就是少了if (i startIndex nums[i] nums[i - 1]) continue这一行。LeetCode 40“组合总和II”是组合问题候选数组有重复元素要求每个数字在每个组合中只能使用一次并且解集不能包含重复组合。去重逻辑和子集II一样但多了一个条件如果当前和sum nums[i] target则跳过。另外递归是backtrack(i 1)因为每个数字只能用一次。LeetCode 47“全排列II”则是排列问题所有元素都要用上但要返回不重复的全排列。排列问题和组合/子集问题的去重方式略有不同因为排列问题不存在startIndex这个概念每一层都是从0开始遍历所以需要借助used数组来判断当前元素是否已经在路径中同时再用nums[i] nums[i - 1] !used[i - 1]来跳过同层重复。我把这三道题的要点整理成一张表方便对比题目类型排序去重条件下一次递归78 子集子集不需要无需去重i 190 子集II子集需要i startIndex nums[i] nums[i-1]i 140 组合总和II组合需要同左加剪枝i 147 全排列II排列需要!used[i-1]从0开始全遍历4.3 这类题目的通用套路刷多了你会发现子集、组合、排列这三类问题的代码骨架是高度相似的可以抽象成一套模板void backtrack(参数) { if (满足结束条件) { result.add(new ArrayList(path)); return; } for (int i startIndex; i nums.length; i) { // 去重逻辑可选 if (i startIndex nums[i] nums[i - 1]) continue; // 剪枝逻辑可选 // 做选择 path.add(nums[i]); // 递归 backtrack(i 1); // 排列题这里从0开始 // 撤销选择 path.remove(path.size() - 1); } }你去刷任何一道子集/组合/排列题都可以先套这个模板再根据题目条件往里面填“结束条件”“去重条件”“剪枝条件”。这个套路熟练之后LeetCode上相关的几十道中等题基本都是一通百通。关于这道题我个人的经验是不要急着背代码先自己画一遍树形图把[1,2,2]的完整回溯过程手写出来再对照代码走两遍。坚持这个习惯你对“同层去重”的理解会远超那些只刷了三遍代码的同学。后续再遇到需要去重的变种题你会发现自己根本不需要查题解就能写对。