感觉这么写会更好懂一点

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end()); // 把所有相同的数放在一起，方便后续处理
        dfs(nums, 0);
        return res;
    }

    void dfs(vector<int>& nums, int u)
    {
        res.push_back(path);
        for (int i = u; i < nums.size(); i ++)
        {
            path.push_back(nums[i]);
            dfs(nums, i + 1);
            path.pop_back();
            // 只要前一个数和后一个数相同，就不再遍历这个数
            while (i + 1 < nums.size() && nums[i] == nums[i + 1]) ++ i;
        }
    }
};

excellent

very excellent

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    int n;
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        //先排序，把所有相同的元素放在一起，之后统计相同元素个数，对于每个相同元素可以选择的次数为0-t(t表示元素出现次数)
        //将所有元素的所有次数可能相互组合即可得到所有解集
        sort(nums.begin(), nums.end());
        n = nums.size();
        dfs(nums, 0);
        return res;
    }

    void dfs(vector<int>& nums,int u){
        if(u == n){
            res.push_back(path);
            return;
        }

        int k = 0;  //k表示当前元素出现次数
        while(u + k < n && nums[u] == nums[u + k]) k ++;

        //i <= k是有等号的，i = 0时表示一个元素都不放，i = k时表示已经放了k个元素，i == k这个条件需要好好体会一下
        for(int i = 0; i <= k; i++){
            dfs(nums, u + k);
            path.push_back(nums[u]);
        }

        //弹出k + 1个元素，因为push了k + 1个nums[u]
        for(int i = 0; i <= k; i ++) path.pop_back();
    }
};

y总在19暑期打卡的写法

这种算法的时间复杂度多少呀？

dfs里面那个主循环没看懂。。。为什么先dfs再push_back呢

i = 0 和 i = k又应该怎么更进一步地理解……

我明白了！谢谢你的注释

class Solution {
public:
    vector<vector<int>> ans;
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<int> path;
        sort(nums.begin(), nums.end());
        dfs(0,path,nums);
        return ans;
    }
    void dfs(int u, vector<int> &path, 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,path,nums);
            path.pop_back();
        }
    }
};

class Solution {

    private List<List<Integer>> res = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        if (nums == null || nums.length == 0) {
            return res;
        }

        Arrays.sort(nums);
        dfs(nums, 0);

        return res;
    }

    private void dfs(int[] nums, int index) {
        res.add(new ArrayList<>(path));

        for (int i = index; i < nums.length; i ++) {
            if (i > index && nums[i-1] == nums[i]) continue;

            path.add(nums[i]);
            dfs(nums, i + 1);
            path.remove(path.size() - 1);
        }
    }
}

没太理解后面恢复现场的操作，请问erase掉的元素是相同的几个元素吗？for循环里面不是已经考虑过一个都不选的情况了吗，为啥还要erase？

没懂为甚么这样做

erase是去重吗

这里是回溯里的恢复现场操作，递归结束后需要将path数组恢复原状 。

明白了，大佬牛逼

y总牛逼，有个语法小问题，当nums为空时 ，dfs会执行一个ans.push_back(path) 操作，虽然path为空vector，但是此时ans当长度为1 不为空了，按理我们应该返回一个长度为0的ans才对啊

空集也算一个集合，这道题目的样例中给出了返回空集的情况。

对的对的，我漏看了，y总牛逼！

看不懂....,还是用set去重吧,智商不够 :-(

也是可以的，不过运行效率稍微低一些。
上面的算法简单来说，就是先枚举所有不同的数，然后再枚举每个数可以选多少个。

存储答案时还需要 O(n) 的计算量是指每次把path中的元素拷贝到ans中的计算量吗？

是的。在C++中 push_back 函数会把数组中的元素都复制一遍，需要 $O(n)$ 的计算量。
我们也可以避免掉这里的计算量，方法是每次直接在ans中维护方案。

计算直接从ans中维护方案，每个path的复杂度也是O(n)吧，最终的ans中数字个数就是2^n*n的量级，应该没法避免

应该是O(n2^n)? （毕竟78这道弱的版本是O(n2^n)了）

没错，已改。
另外需要注意一下这两道题目算法的区别，如果不要求记录方案，则弱化版由于是用二进制来做的，两重循环，时间复杂度仍是 $O(n2^n)$；但这道题目是用递归做的，总共递归到的节点个数是 $2 \times 2^n - 1$个，所以时间复杂度是 $O(2^n)$。