78. 子集

递归

class Solution {
    private List ls; 
    private boolean []bool;
    private int n;
    public List> subsets(int[] nums) {
        n = nums.length;
        ls = new LinkedList();
        if(n==0)return ls;
        bool = new boolean [n];
        dfs(nums,0,bool);
        return ls;
    }
    public void dfs(int nums[],int u,boolean bool[]) {
        if(u==n) {
            LinkedList path = new LinkedList();
            for(int i = 0 ; i< n ;i++) {
                if(bool[i]==false)
                    path.add(nums[i]);
            }
            ls.add(path);
        }
        else {
            bool[u]= true;
            dfs( nums,u+1,bool);
            bool[u] = false;
            dfs( nums,u+1,bool);
        }
    }
}

回溯+二进制

class Solution {
    private List ls;
    private boolean[] bool;
    private int n;
    public List> subsets(int[] nums) {
        n = nums.length;
        ls = new LinkedList();
        bool = new boolean[n];
        for (int i = 0; i < Math.pow(2, n); i++) {
            LinkedList path = new LinkedList();
            String s = Integer.toBinaryString(i);
            while(s.length()!=n) s = '0'+s;
            for (int x = 0; x < n; x++)
                if (s.charAt(x) == '1')
                    path.add(nums[x]);
            ls.add(path);
        }
        return ls;
    }
}