MENU

LeetCode90. 子集 II

July 11, 2018 • Read: 2510 • LeetCode阅读设置

image
升级版子集问题,最简单的办法,先把所有元素存储到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);
}
Last Modified: May 12, 2021
Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment