Question

link

Given a set of distinct integers, S, return all possible subsets.

Note:

  • Elements in a subset must be in non-descending order.
  • The solution set must not contain duplicate subsets.

For example,
If S = [1,2,3], a solution is: 

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]


      </div>

Stats

Frequency 4
Difficulty 3
Adjusted Difficulty 4
Time to use --------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Solution

This is a classic DFS problem. This problem is easily solved by recursive calls. But recursion is always not the best solution.

A popular solution is (since elements got no duplications) adding elements 1 by 1. That is to say, get previous answer, add each list by a new element, and then add each new list back to answer. Continue until all elements are added in sequence. For example:

Initialize the subset: {}

Added element “1”: {}, {“1”}

Added element “2”: {}, {“1”}, {“2”}, {“1”, “2”}

Added element “3”: {}, {“1”}, {“2”}, {“1”, “2”}, {“3”}, {“1”,”3”}, {“2”,”3”}, {“1”, “2”,”3”}

I found a very interesting bit operation solution, and I will also post it below.

Code

First, recursion. This solution is trivial and boring.

public ArrayList<ArrayList<Integer>> subsets(int[] S) {
    ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
    if (S.length == 0) {
        ans.add(new ArrayList<Integer>());
        return ans;
    }
    Arrays.sort(S);
    int head = S[0];
    int[] theRest = new int[S.length - 1];
    for (int i = 0; i < theRest.length; i++) {
        theRest[i] = S[i + 1];
    }
    ArrayList<ArrayList<Integer>> subAns = subsets(theRest);
    for (ArrayList<Integer> oneSet: subAns) {
        ArrayList<Integer> longerOneSet = new ArrayList<Integer>();
        longerOneSet.add(head);
        for (Integer a: oneSet) {
            longerOneSet.add(a);
        }
        ans.add(longerOneSet);
        ans.add(oneSet);
    }
    return ans;
}

Second, add elements 1 by 1

public ArrayList<ArrayList<Integer>> subsets(int[] S) {
    ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
    ans.add(new ArrayList<Integer>());
    Arrays.sort(S);
    for (int i = 0; i < S.length; i ++) {
        int curSize = ans.size();
        for (int j = 0; j < curSize; j ++) {
            ArrayList<Integer> cur = new ArrayList<Integer>(ans.get(j));
            cur.add(S[i]);
            ans.add(cur);
        }
    }
    return ans;
}

Third, bit operations

public ArrayList<ArrayList<Integer>> subsets(int[] S) {
    ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
    Arrays.sort(S);
    int N = S.length;
    for (int i = 0; i < Math.pow(2, N); ++i) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        for (int j = 0; j < N; ++j) {
            if ((i & (1 << j)) > 0) {
                list.add(S[j]);
            }
        }
        ans.add(list);
    }
    return ans;
}

Updated on June 12th - solution using the ‘Permutation Model’.

public List<List<Integer>> subsets(int[] num) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    if(num == null || num.length == 0) {
        return result;
    }
    Arrays.sort(num);
    helper(result, new LinkedList<Integer>(), num, 0);
    return result;
}

private void helper(List<List<Integer>> ans, List<Integer> path, int[] num, int position) {
    ans.add(new LinkedList<Integer>(path));
    for (int i = position; i < num.length; i ++) {
        path.add(num[i]);
        helper(ans, path, num, i + 1);
        path.remove(path.size() - 1);
    }
}