90. 子集II

给你一个整数数组 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

题解1：弱智回溯法，出自我手
其实我是先写出来这个之后再去做的子集I。没办法，一开始位运算看不懂。

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> results = new ArrayList<List<Integer>>();
        results.add(new ArrayList<Integer>());
        for(int i=0;i<nums.length;++i){
            List<List<Integer>> increase = new ArrayList<List<Integer>>();
            for (List list : results) {
                List<Integer> newList = new ArrayList<Integer>();
                newList.addAll(list);
                newList.add(nums[i]);
                if(!results.contains(newList))
                    increase.add(newList);
            }
            results.addAll(increase);
        }
        return results;
    }
}

题解2：位运算回溯法
核心思想：将数组排序后，只有当当前下标的元素与前者相同时才有可能产生重复的情况。具体来说是前一位元素下标在当前mask的取值为0时。比方说给定数组1，2，2。当前mask为100（需要颠倒过来看，表示取第三位，舍弃前两位），那么当前mask需要被滤去，因为重复了（010会指向同一结果）。那么如何判断呢？我们需要把mask右移一（当前判断第三位因此i=2，i-1=1）位，看看是不是0（与1做与运算就可以达到）。如果是0，就舍去。

class Solution {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    List<Integer> increase = new ArrayList<Integer>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        int n=nums.length;
        Boolean flag;
        for(int mask=0;mask<1<<n;++mask){
            increase.clear();
            flag = true;
            for(int i=0; i<n;++i){
                if ((mask&1<<i) != 0){
                    if (i>0 && nums[i]==nums[i-1] && (mask>>(i-1)&1)==0){
                        flag = false;
                        break;
                    }
                    increase.add(nums[i]);
                }
            }
            if (flag)
                result.add(new ArrayList<Integer>(increase));
        }
        return result;
    }
}

题解3：递归回溯法

class Solution {
    List<Integer> t = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        dfs(false, 0, nums);
        return ans;
    }

    public void dfs(boolean choosePre, int cur, int[] nums) {
        if (cur == nums.length) {
            ans.add(new ArrayList<Integer>(t));
            return;
        }
        dfs(false, cur + 1, nums);
        if (!choosePre && cur > 0 && nums[cur - 1] == nums[cur]) {
            return;
        }
        t.add(nums[cur]);
        dfs(true, cur + 1, nums);
        t.remove(t.size() - 1);
    }
}