90. 子集 II

难度 medium
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1：

输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

1 <= nums.length <= 10
-10 <= nums[i] <= 10

解题思路：这道题是另一道题目78.子集的改动版，我看了grandyang的解法，然后用java写了一遍，有点坑，贴出来注意一下。首先res里面有一个空数组[[]]，然后我们开始遍历给定的nums,这个时候就是和刚提到的题目一个思路，首先遍历res，把遍历到的每个元素先加上当前的nums[i]，再重新添加到res中，也即[[]], [[],[1]], [[],[1],[2],[1,2]],...,前面和上一道题是一样的，如果出现重复的数，应该怎么处理呢？我们注意到，当第二个2来的时候，明显对当前res[[],[1],[2],[1,2]]，我们不用从[]开始遍历，因为这一部分和上一个2出现的时候的情况是一样的，开始的地方应该是从[2]这里，这个[2]前面的数组我们不用再添加当前的2了，因此，我们用size记录上一轮res的大小，并且用last记录上一个添加进来的元素（nums[i]），如果当前遍历的nums和last不相等，那么我们从res的第0位开始操作，而如果相等，我们用当前res的大小减去size，也就是上个相同元素添加进来之前res的大小，从而把重复的[],[1]那一部分跳过去，然后进行遍历，也就是从[2]开始。

代码 t100 s20 java

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums.length==0) return res;
        Arrays.sort(nums);
        res.add(new ArrayList<Integer>());
        int last = nums[0], size = 1;
        for(int i=0; i<nums.length; i++){
            if(last!=nums[i]){
                last = nums[i];
                size = res.size();
            }
            int newSize = res.size();
            for(int j=newSize-size; j<newSize; j++){
                // res.add((ArrayList)res.get(j));
                // res.get(res.size()-1).add(nums[i]);
                List<Integer> temp = new ArrayList<>(res.get(j));
                temp.add(nums[i]);
                res.add(temp);
            }
        }
        return res;
    }
}

注释的两行是开始写的，但是后面发现get回来的数组只是个引用，添加新元素后原来位置的数组也被改变了，导致最后出现的结果就是[[1,2,2,2], [1,2,2,2], [1,2,2,2], [1,2,2,2], [1,2,2,2], [1,2,2,2]]，因此还是要用创建新数组的方法，并用get到的数组来初始化新数组，再往里面添加nums[i]。下面是3个月前提交的cpp解法，来自grandyang
代码 t67 s76 cpp

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

参考资料：
https://www.cnblogs.com/grandyang/p/4310964.html

90. 子集 II

原文：https://www.cnblogs.com/zhengxch/p/14600363.html