LeetCode 90. 子集 II

class Solution {
public:
    unordered_map<int ,int> cnt;
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        for(auto i:nums)
            cnt[i]++;
        dfs(-10);//从-10开始枚举每一个数
        return res;
    }
    void dfs(int u)
    {
        if(u>10)
        {
            res.push_back(path);
            return ;
        }
        for(int i=0;i<cnt[u]+1;i++)//枚举每一个数选i个的情况
        {
            dfs(u+1);
            path.push_back(u);
            //第一次递归时，path是没有加入数字u的，第i递归path加入了i-1个数字u
        }
        //退出循环时，需要恢复现场，此时已经加入了cnt[u]个数字u
        for(int i=0;i<cnt[u]+1;i++)
            path.pop_back();
    }
};