LeetCode-90. 子集 II

素颜马尾好姑娘i 2024-03-26 14:24 55阅读 0赞

题目来源  
[90. 子集 II][90. _ II]

### 题目思路 ###

建议先把这两道题做了，在做这道  
[40.组合总和II][40._II]  
[78. 子集][78.]  
这道题目和78.子集区别就是集合里有重复元素了，而且求取的子集要去重。  
那么关于回溯算法中的去重问题，在40.组合总和II和本题是一个套路。  
用示例中的\[1, 2, 2\] 来举例，如图所示： （注意去重需要先对集合排序）  
![在这里插入图片描述][5c73a8f24b1b483eb5680f1cdabe2307.png]  
从图中可以看出，同一树层上重复取2 就要过滤掉，同一树枝上就可以重复取2，因为同一树枝上元素的集合才是唯一子集！

### 代码实现 ###

class Solution {
        
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        boolean[] used;
        public List<List<Integer>> subsetsWithDup(int[] nums) {
        
            if(nums == null || nums.length == 0){
        
                return result;
            }
            used = new boolean[nums.length];
            Arrays.sort(nums);
            backTracking(nums,0,used);
            return result;
        }
        private void backTracking(int[] nums,int startIndex,boolean[] used){
        
            result.add(new ArrayList(path));
    
            if(startIndex == nums.length){
        
                return;
            }
    
            for(int i = startIndex;i<nums.length;i++){
        
                if(i>0 && nums[i] == nums[i-1] && !used[i-1]){
        
                    continue;
                }
                path.add(nums[i]);
                used[i] = true;
                backTracking(nums,i+1,used);
                used[i] = false;
                path.remove(path.size()-1);
    
            }
        }
    
    }

![在这里插入图片描述][59735debc6844f63bc1e922f2e301d70.png]

[90. _ II]: https://leetcode.cn/problems/subsets-ii/
[40._II]: https://donglin.blog.csdn.net/article/details/129149114
[78.]: https://donglin.blog.csdn.net/article/details/129196786
[5c73a8f24b1b483eb5680f1cdabe2307.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/2dce739d31b2414ebb65411c944d4013.png
[59735debc6844f63bc1e922f2e301d70.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/d7d2afcf06ae4b43a3a61cda26287926.png