My solution using results doubling

  • 0

    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));
    public List<List<Integer>> subsets(int[] S) {
        if(S == null) { return null; }
        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.