leetcode90. 子集 II

分析

由于有重复元素，那么遍历时会产生重复序列，可以先对数组排序，然后如果dfs遇到与上次相同的数字跳过此次循环。

class Solution {
public:
    vector<int> path;
    vector<vector<int>> ans;
    void dfs(int u,vector<int>& nums){
        ans.push_back(path);
        for(int i=u;i<nums.size();i++){
            if(i>u&&nums[i]==nums[i-1])continue;
            path.push_back(nums[i]);
            dfs(i+1,nums);
            path.pop_back();
        }
        return ;
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        dfs(0,nums);
        return ans;
    }
};