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而不是理论上限空间上更是要先把这堆重复结果全部存下来再筛。以n20为例如果全是不重复元素结果集有约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 { ListListInteger res new ArrayList(); LinkedListInteger path new LinkedList(); public ListListInteger 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)。空间复杂度方面递归栈深度最大为npath长度不超过n结果集存储的是答案本身不计入辅助空间所以辅助空间是O(n)。用哈希版本的话每层多一个集合最差也是O(n)量级不变但要常数更大。如果你在面试里被追问这个2^n是怎么来的可以这样回答每个元素在一条搜索路径上只有选或不选两种决策决策树的叶子节点就有2^n个再加上中间节点也是子集总状态数不超过2^(n1)。这个推导既清晰又严谨比死记公式强。5.2 两大易混点为什么不能用contains去重为什么输入不必有序第一个问题能不能在递归里用if nums[i] in path来去重绝对不能。path里存的是数值path中有一个2不代表这一层不能再选2。[2,2]这个子集本身就要求连续选两个2。你要去重的是同一层已经以相同数值展开过分支而不是当前路径中是否含该值。这两者一个管横向一个管纵向混为一谈就是低级错误。第二个问题输入有序到底意味着什么意味着我们可以用比较相邻元素的方式识别重复。如果题目给的是无序数组且要求相对顺序不被打乱那就回归哈希版本。90题支持排序所以最简单。5.3 和LeetCode 40、78、491的对照核心逻辑一模一样我把这四题的关系总结成一张表方便你在刷题时建立知识网络题目核心区别去重方式关键点78. 子集无重复元素无需去重回溯入门模板90. 子集II有重复但不允许重复子集排序 同层跳过树层去重40. 组合总和II和为target且元素不可重复使用排序 同层跳过额外加sum剪枝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剪枝题你都能在十分钟内定位核心思路。 LeetCode 90 子集II：回溯去重核心模板与树层剪枝详解
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而不是理论上限空间上更是要先把这堆重复结果全部存下来再筛。以n20为例如果全是不重复元素结果集有约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 { ListListInteger res new ArrayList(); LinkedListInteger path new LinkedList(); public ListListInteger 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)。空间复杂度方面递归栈深度最大为npath长度不超过n结果集存储的是答案本身不计入辅助空间所以辅助空间是O(n)。用哈希版本的话每层多一个集合最差也是O(n)量级不变但要常数更大。如果你在面试里被追问这个2^n是怎么来的可以这样回答每个元素在一条搜索路径上只有选或不选两种决策决策树的叶子节点就有2^n个再加上中间节点也是子集总状态数不超过2^(n1)。这个推导既清晰又严谨比死记公式强。5.2 两大易混点为什么不能用contains去重为什么输入不必有序第一个问题能不能在递归里用if nums[i] in path来去重绝对不能。path里存的是数值path中有一个2不代表这一层不能再选2。[2,2]这个子集本身就要求连续选两个2。你要去重的是同一层已经以相同数值展开过分支而不是当前路径中是否含该值。这两者一个管横向一个管纵向混为一谈就是低级错误。第二个问题输入有序到底意味着什么意味着我们可以用比较相邻元素的方式识别重复。如果题目给的是无序数组且要求相对顺序不被打乱那就回归哈希版本。90题支持排序所以最简单。5.3 和LeetCode 40、78、491的对照核心逻辑一模一样我把这四题的关系总结成一张表方便你在刷题时建立知识网络题目核心区别去重方式关键点78. 子集无重复元素无需去重回溯入门模板90. 子集II有重复但不允许重复子集排序 同层跳过树层去重40. 组合总和II和为target且元素不可重复使用排序 同层跳过额外加sum剪枝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剪枝题你都能在十分钟内定位核心思路。