My solution using results doubling


  • 0
    I

    The idea is similar to bit manipulation, but I used a recursive fashion.
    If (n-1) has a subset list SS = {S1, S2, ... Sm}, n's subset should like this. The first half is still SS, and the second half is adding nth element to each items in SS. The result is combine {S1, S2, ... Sm} with {{S1,nth}, {S2,nth}, ... {Sm,nth}}

    public void helper(List<List<Integer>> lists, int val) {
        int sz = lists.size();
        for(int i = 0; i < sz; i++) {
            List<Integer> tmp = new ArrayList<Integer>(lists.get(i));
            tmp.add(val);
            lists.add(tmp);
        }
    }
    
    public List<List<Integer>> subsets(int[] S) {
        if(S == null) { return null; }
        
        Arrays.sort(S);
        
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        res.add(new ArrayList<Integer>()); //the seed
        
        for(int s : S) {
            helper(res, s);
        }
        return res;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.