【回溯】子集Ⅱ

子集 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
        }
    }

};
           

運作如下：