LeetCode90.子集 ||

题目

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。

分析

在LeetCode78.子集基础上的变形，解题思路来源 LeetCode40.组合总和II，这两个题目的核心就是，给定可能包含重复元素的集合，如何将结果去重？利用 used数组 +排序（勿忘）

在搜索树中同分支可以有重复，但同层不能有重复。因为同层出现重复，意味着结果可能会有重复。新开一个数组 used ，来标记元素使用情况。nums[i] == nums[i-1] 的情况下，如果 used[i - 1] == true ，说明同一树支上有重复使用。如果 used[i - 1] == false，说明同层出现重复，这种情况要不做操作，因为之前已经处理过该元素。

代码

 1 class Solution {
 2 public:
 3     vector<int>path;
 4     vector<vector<int>>res;
 5     void backtracking(vector<int>nums,int startIndex,vector<bool>used){
 6         res.push_back(path);
 7         if(startIndex == nums.size()){
 8             return;
 9         }
10         for(int i = startIndex;i < nums.size();i++){
11             if(i > 0 && nums[i] == nums[i-1] && used[i-1] == false) continue;
12             used[i] = true;
13             path.push_back(nums[i]);
14             backtracking(nums,i+1,used);
15             path.pop_back();
16             used[i] =false;
17         }
18     }
19     vector<vector<int>> subsetsWithDup(vector<int>& nums) {
20         sort(nums.begin(),nums.end());  //先排序，让重复元素挨在一起
21         vector<bool>used(nums.size(),false);
22         backtracking(nums,0,used);
23         return res;
24     }
25 };