LeetCode90. 子集 II

阳光穿透心脏的1/2处 2022-11-15 12:23 94阅读 0赞

难度：`中等`  
题目描述：  
给你一个整数数组 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

解题思路：  
[参考][Link 1]  
元素在同一个组合内是可以重复的，怎么重复都没事，但两个组合不能相同。

所以我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。

剧透一下，后期要讲解的排列问题里去重也是这个套路，所以理解“树层去重”和“树枝去重”非常重要。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW9rdWRlenR0_size_16_color_FFFFFF_t_70]

class Solution { 
    public:
        vector<vector<int>> ans;
        vector<int>tmp;
        void backtracking(vector<int>& nums,int start,vector<int> &used){ 
            ans.push_back(tmp);
            for(int i=start;i<nums.size();i++){ 
                if(i>0&&nums[i]==nums[i-1]&&used[i-1]==0){ 
                    continue;
                }
                tmp.push_back(nums[i]);
                 // used[i - 1] == 1，说明同一树支candidates[i - 1]使用过
                // used[i - 1] == 0，说明同一树层candidates[i - 1]使用过
                // 而我们要对同一树层使用过的元素进行跳过
                used[i]=1;
                backtracking(nums,i+1,used);
                used[i]=0;
                tmp.pop_back();
            }
        }
        vector<vector<int>> subsetsWithDup(vector<int>& nums) { 
            int n=nums.size();
            vector<int>used(n,0);
            sort(nums.begin(),nums.end());
            backtracking(nums,0,used);
            return ans;
        }
    };

[Link 1]: https://leetcode-cn.com/problems/subsets-ii/solution/90-zi-ji-iiche-di-li-jie-zi-ji-wen-ti-ru-djmf/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW9rdWRlenR0_size_16_color_FFFFFF_t_70]: /images/20221022/aaae6bbbf9fb4c91af5d7c6ba37f3806.png