90. 子集 II

[Ni-Guvara]

class Solution {
private:
    vector<vector<int>> res;
    vector<int> path;
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        int len = nums.size();
        std::sort(nums.begin(), nums.end());
        backtracing(nums , 0 , len);
        return res;
    }

    void backtracing(vector<int> & nums ,int startIndex , int len)
    {
        res.push_back(path);
        if(startIndex >= len)
            return;
        for(int i = startIndex ; i < len ;i++)
        {
            if( i > startIndex && nums[i] == nums[i-1])   
                continue;
            path.push_back(nums[i]);
            backtracing(nums , i + 1  , len);
            path.pop_back();
        }

    }

};

[Ni-Guvara]

直接去重

[Ni-Guvara]

class Solution {
private:
    set<vector<int>> res;
    vector<int> path;
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        int len = nums.size();
        std::sort(nums.begin(), nums.end());
        backtracing(nums , 0 , len);

        vector<vector<int>> ans(res.begin(),res.end());
        return ans;
    }

    void backtracing(vector<int> & nums ,int startIndex , int len)
    {
        res.insert(path);
        if(startIndex >= len)
            return;
        for(int i = startIndex ; i < len ;i++)
        {
            path.push_back(nums[i]);
            backtracing(nums , i + 1 , len);
            path.pop_back();
        }

    }

};

[Ni-Guvara]

使用hash