MENU

LeetCode78.子集

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

image

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,int n){
        if(idx >= n) {
            List<Integer> tmp = new ArrayList<Integer>();
            for(int i = 0;i < n;i++) {
                if(v[i]) 
                    tmp.add(nums[i]);
            }    
            ans.add(tmp);
            return;
        }
        v[idx] = true;
        dfs(idx + 1,nums,n);//yes
        v[idx] = false;
        dfs(idx + 1,nums,n);//no
    }
    public List<List<Integer>> subsets(int[] nums) {
        ans.clear();
        int n = nums.length;
        dfs(0,nums,n);
        return ans;
    }
}

dfs经典题,对每一个数字都有一个boolean数组去对应,没选过就是false,选过就是true,在边界条件中进行枚举,将所有结果为true的下标对应的数值添加到List中即可

不好想的地方在于递归的部分,每个数都可以选或者不选,那么如何来表示选,选了就将v[idx]标记为true,不选就将v[idx]标记为false,不论选还是不选,都要进行递归

Last Modified: May 12, 2021
Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment