LeetCode90. 子集 II

升级版子集问题，最简单的办法，先把所有元素存储到 set 中去重，然后再重新赋值给数组，再 dfs，但这样做太简单了，没什么难度，于是换了一种做法，不去重，直接 dfs

class Solution {
    public static List<List<Integer>> ans = new ArrayList<List<Integer>>();
    public static boolean[] v = new boolean[100];
    public static void dfs(int idx,int[] nums) {
        //[1,2,2]
        if(idx >= nums.length) {
            List<Integer> tmp = new ArrayList<Integer>();
            for(int i = 0;i < nums.length;i++) 
                if(v[i])
                    tmp.add(nums[i]);
                ans.add(tmp);
            return;
        }
        if(idx > 0 && nums[idx - 1] == nums[idx] && !v[idx - 1]) {
            v[idx] = false;
            dfs(idx + 1,nums);//no
        } else {
            v[idx] = true;
            dfs(idx + 1,nums);//yes
            v[idx] = false;
            dfs(idx + 1,nums);//no
        }
        
    }
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        ans.clear();
        int n = nums.length;
        for(int i = 0;i < n;i++) 
            for(int j = i + 1;j < n;j++)
                if(nums[j] > nums[i]) {
                    int t = nums[i];
                    nums[i] = nums[j];
                    nums[j] = t;
                }
        dfs(0,nums);
        return ans;
    }
}

dfs 函数前面都是正常的套路了，主要是后面的判断，如果前面元素的值和我当前搜索到的值一样，并且前面的那个数值没选过，那我这次就选。

举个例子，假设有数组 [2,2,2,2,2]，以 0 表示不选，1 表示选，那么可能的情况就有 [1,0,0,......],[1,1,0,......]......，但是绝对不能出现 [0,1,...] 这种 [0,1] 序列，因为会和 [1,0...] 这种序列重复，所以当上一个值没选，那么当前的值如果和它相同，当前的值也不能选，对应的就是这段代码片：

if(idx > 0 && nums[idx - 1] == nums[idx] && !v[idx - 1]){
    v[idx] = false;
    dfs(idx + 1,nums);
}