LeetCode 90 Subsets II 回溯()

Given an integer array that may contain duplicates, return all possible subsets (the power set).

nums

The solution set must not contain duplicate subsets. Return the solution in any order.

Solution

如何处理相同的子集:先把 \(vector\) \(sort\) 一下,然后在 \(ans\) 里面 \(find\), 依旧记得擦除标记

class Solution {
private:
    vector<vector<int>> ans;
    vector<int> res;
    
    
    void dfs(vector<int> nums, vector<int>&res, int pos){
        
        for(int i=pos; i<nums.size();i++){
            res.push_back(nums[i]);
            
            vector<int> tmp = res;
            
            sort(res.begin(), res.end());
            if(find(ans.begin(), ans.end(), res) == ans.end()){
                // not repeated
                ans.push_back(res);
            }
            dfs(nums, res, i+1);
            res = tmp;
            res.pop_back();
        }
    }
    
    
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        ans.push_back(res);
        dfs(nums, res, 0);
        return ans;
    }
};
————————

Given an integer array that may contain duplicates, return all possible subsets (the power set).

nums

The solution set must not contain duplicate subsets. Return the solution in any order.

Solution

如何处理相同的子集:先把 \(vector\) \(sort\) 一下,然后在 \(ans\) 里面 \(find\), 依旧记得擦除标记

class Solution {
private:
    vector<vector<int>> ans;
    vector<int> res;
    
    
    void dfs(vector<int> nums, vector<int>&res, int pos){
        
        for(int i=pos; i<nums.size();i++){
            res.push_back(nums[i]);
            
            vector<int> tmp = res;
            
            sort(res.begin(), res.end());
            if(find(ans.begin(), ans.end(), res) == ans.end()){
                // not repeated
                ans.push_back(res);
            }
            dfs(nums, res, i+1);
            res = tmp;
            res.pop_back();
        }
    }
    
    
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        ans.push_back(res);
        dfs(nums, res, 0);
        return ans;
    }
};