Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: [1,2,2]
Output:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

AC代码

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        if (nums.empty()) return {};
        sort(nums.begin(), nums.end());
        vector<vector<int>> res{{}};
        vector<int> t;
        int k = 0;
        for (int i = 0; i < nums.size(); ++i) {
            int size = res.size();
            int j = 0;
            if (i > 0 && nums[i] == nums[i - 1]) j = res.size() - k;
            k = 0;
            for (; j < size; j++) {
                res.push_back(res[j]);
                res.back().push_back(nums[i]);
                k++;
            }
        }
        return res;
    }
};

总结

基于没有重复值求子集的一个方法：（78题中有写）
1、创建一个只有空集的vector<vecor<int>> res
2、nums有n个数，做n次循环
3、对每次循环，复制已在res里的vecor<int>,在末尾添加nums[i]后作为新元素添加到res
如果有重复值，上述第3步骤就要改，不能复制res中所有已有的元素然后添加当前nums[i]，只能在上次循环中新加入的vector<int>后面添加nums[i]，用k记录上次循环添加了多少新内容，然后用res.size()-k得到正确的起始下标