【LeetCode刷题日记】90.子集Ⅱ--- 归纳题解

个人主页代码不加冰欢迎来访作者简介java后端学习者❄️个人专栏LeetCode刷题日记 苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺前言大家好我是代码不加冰今天是高考的最后一天感觉还是有点感慨的去年的这时候我又是什么心情的可能是难以言表的并没有想象中的兴奋激动但也不是解脱吧高考完还是有一堆的事成绩考的好不好志愿怎么报总之没我们想象中的那么好有一句话说的挺好人总是在接近幸福时最幸福好比是周末最幸福的时候往往是星期五的下午。所以我们没有必要对未来太过期待沉下心来切实的享受当下用内心去体验不追怀过去也不遥想未来。可能这样算是既不悲观也不乐观每天都是平平淡淡但是总有那一瞬间我们会发现蕴藏在日常生活中的那种幸福感是来自内心深处的填充这些以后有时间再讲讲吧让我们进入到每日的刷题环节。摘要本文通过力扣90题子集Ⅱ深入解析回溯算法中的去重问题。作者首先指出本题与子集I的区别在于处理重复元素并回顾了组合总和II的去重技巧。重点区分了树层去重防止同一层重复元素产生重复子集和树枝去重防止同一路径重复使用元素通过[1,2,2]示例详细演示了未去重时会产生[2]重复子集的情况。文章对比了used数组在全排列题和子集题中的不同应用强调子集问题通过startIndex排序实现树层去重即可。最后总结了used数组在树层/树枝判断中的核心作用帮助读者掌握回溯去重的本质逻辑。题目背景90.子集Ⅱ给你一个整数数组nums其中可能包含重复元素请你返回该数组所有可能的 子集幂集。解集不能包含重复的子集。返回的解集中子集可以按任意顺序排列。示例 1输入nums [1,2,2]输出[[],[1],[1,2],[1,2,2],[2],[2,2]]示例 2输入nums [0]输出[[],[0]]提示1 nums.length 10-10 nums[i] 10题目分析这道题目和78.子集 区别就是集合里有重复元素了而且求取的子集要去重。那么关于回溯算法中的去重问题在40.组合总和II 中已经详细讲解过了和本题是一个套路。这里我们主要复习一下这些易混淆的知识让我们加深印象答案是次要的。一、什么是树层去重代码中的if (i startIndex nums[i] nums[i - 1]) { continue; }就是树层去重。以nums [1,2,2]为例[] / | \ 1 2 2第一层中第一个2可以选第二个2不能选因为i startIndex nums[i] nums[i-1]成立。否则会产生[] ├─ 2 └─ 2两个完全一样的分支。所以同一层中相同元素只保留第一个。二、什么是树枝去重树枝去重是同一个路径上不允许重复使用某个元素。例如全排列 II力扣47boolean[] used;里面会写if (used[i]) continue;意思是1 → 2 → 1第二次使用同一个位置的1不允许。这里限制的是当前路径树枝而不是当前层。三、画图理解树层同一个父节点的孩子[] / | \ 1 2 2这一排叫同一树层树枝从根到叶子的一条路[] | 1 | 2 | 2这条线叫树枝四、为什么90题必须树层去重假设没有去重nums [1,2,2]会得到[] ├─ 2(第一个) └─ 2(第二个)然后[2]会出现两次。所以要把第二个2剪掉。即if(i startIndex nums[i] nums[i-1])五、为什么不是树枝去重如果写成if(i 0 nums[i] nums[i-1]) continue;那么[] └─ 2 └─ 2第二个2也会被剪掉。结果[2,2]这个合法答案没了。因为子集允许同时选两个2。所以[2] ↓ [2,2]这条树枝必须保留。六、一个经典口诀树层去重if(i startIndex nums[i] nums[i-1])作用同层相同元素只选一次常见题力扣90 子集II力扣40 组合总和II力扣491 递增子序列树枝去重if(used[i])作用当前路径上同一个元素不能重复使用常见题力扣46 全排列力扣47 全排列II一句话区分树层去重防止结果重复。树枝去重防止同一个元素在一条路径上被重复使用。举例分析对于力扣90记住if(i startIndex nums[i] nums[i-1])这是标准的树层去重写法。因为题目允许得到[2,2]所以绝不能把树枝上的第二个2剪掉。这题就算选了没有树层去重会产生什么结果举例分析很好这题最好的理解方式就是把树层去重删掉然后看看会多出什么结果。假设nums [1,2,2]排序后仍然是[1,2,2]并且把这一句删掉if (i startIndex nums[i] nums[i - 1]) { continue; }回溯树根节点[]第一层[] / | \ 1 2 2 (i0) (i1) (i2)注意第一个2来自下标1第二个2来自下标2虽然来源位置不同但值一样。第一条分支选择第一个2下标1[] └── [2]加入答案[] [2]继续往下[] └── [2] └── [2,2]加入答案[2,2]第二条分支回到根节点。选择第二个2下标2[] └── [2]又得到[2]注意这个[2]和前面的[2]完全一样。最终结果会得到[ [], [1], [1,2], [1,2,2], [1,2], // 重复 [2], [2,2], [2] // 重复 ]其中[1,2]出现两次。[2]出现两次。为什么会重复看根节点[] / | \ 1 2 2 ↑ ↑两个2在同一层。它们生成的子集完全一样选第一个2 → [2] 选第二个2 → [2]所以第二个2的整棵子树都是重复的。树层去重后的效果有了if (i startIndex nums[i] nums[i - 1])在根节点这一层[] / | 1 2第二个2直接跳过。于是[2]只会生成一次。为什么[2,2]不会被去掉很多人这里容易误会。当路径来到[] └── [2]此时startIndex 2循环访问i 2判断i startIndex即2 2结果false不会跳过。所以[] └── [2] └── [2]即[2,2]仍然保留下来。可以记一个判断方法同一层出现两个相同数字 ↓ 保留第一个剪掉后面的 ↓ 树层去重 同一路径上继续选择相同数字 ↓ 允许 ↓ 得到 [2,2]这正是力扣90的核心同层不能重复选同枝可以继续选。used[]数组本质上是在记录某个下标对应的元素当前是否已经在这条递归路径树枝上被使用过。例如nums [1,2,3] boolean[] used new boolean[3];初始used [false,false,false]表示三个元素都还没被选。例子全排列力扣46代码for(int i 0; i nums.length; i) { if(used[i]) continue; used[i] true; path.add(nums[i]); backtracking(nums); path.remove(path.size()-1); used[i] false; }第一层选 1path [1] used [T,F,F]表示下标0已经用过 下标1没用过 下标2没用过第二层循环i0发现used[0] true所以continue;不能再选1。于是只能选2 或 3选2path [1,2] used [T,T,F]第三层此时1 已用 2 已用 3 未用只能选3path [1,2,3] used [T,T,T]得到一个排列。used 数组的作用它解决的问题是同一个元素不能重复使用例如[1,1,1]这种情况不允许。为什么子集题不用 used力扣90backtracking(nums, i 1);每次递归i 1意味着已经访问过的位置 永远不会再访问所以根本不需要used[]used 在力扣47中的另一个用途力扣47全排列Ⅱ有重复数字nums [1,1,2]这里会出现经典代码if(i 0 nums[i] nums[i-1] used[i-1] false) { continue; }很多人看不懂这里的used[i-1]。情况1used[i-1] false第一层 [] / \ 1① 1②如果前面的1没选used[0] false现在又想选第二个1。这说明两个1在同一层属于树层重复。剪掉continue;情况2used[i-1] true[] └── 1① └── 1②前面的1已经在路径上used[0] true此时选第二个1[1,1]合法。不能剪。所以used[i-1] false表示前一个相同元素没有被当前路径使用 ⇒ 同层 ⇒ 去重而used[i-1] true表示前一个相同元素已经在当前路径中 ⇒ 同枝 ⇒ 保留总结used[]有两个常见用途1. 记录元素是否已被当前路径使用用于力扣46 全排列力扣47 全排列Ⅱif(used[i]) continue;防止同一个元素重复加入路径。2. 辅助判断树层/树枝用于if(i0 nums[i]nums[i-1] used[i-1]false)used[i-1]false→ 同层 → 去重used[i-1]true→ 同枝 → 保留而力扣90 子集Ⅱ不需要 used[]因为startIndex已经能区分层次直接用if(i startIndex nums[i] nums[i-1])就完成树层去重了。用示例中的[1, 2, 2] 来举例如图所示 注意去重需要先对集合排序从图中可以看出同一树层上重复取2 就要过滤掉同一树枝上就可以重复取2因为同一树枝上元素的集合才是唯一子集结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励