【回溯】子集Ⅱ

子集 II

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

说明：解集不能包含重复的子集。

示例:

输入: [1,2,2]

输出:

[

  [2],

  [1],

  [1,2,2],

  [2,2],

  [1,2],

  []

]

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/subsets-ii

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目要求添加解集不包括重复的子集，即不能有顺序不相同但元素相同的两个或多个子集，那我们加个去重就好了。

class Solution {
public:
    vector<vector<int>> res;
    vector<int> temp;

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(),nums.end()); //排序
        dfs(nums,0);
        return res;
    }

    void dfs(vector<int>& nums,int cur){
        res.push_back(temp);
        for(int i = cur;i < nums.size();i ++){
            if(i > cur && nums[i-1] == nums[i]) continue; //去重
            temp.push_back(nums[i]); //选cur
            dfs(nums,i + 1);
            temp.pop_back(); //不选cur
        }
    }

};
           

运行如下：