[LeetCode] Subsets

Thought:
We use a number to represent a subset, every bit in this number is 1 or 0. It means for every elements in the set, it should be either in the subset or not.

Code:
public class Solution {
    public ArrayList<ArrayList<Integer>> subsets(int[] S) {
        Arrays.sort(S);
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        int max = 1 << S.length;
        for (int i = 0; i < max; i++) {
            ArrayList<Integer> cache = new ArrayList<Integer>();
            int tmp = i;
            int index = 0;
            while (tmp > 0) {
                if ((tmp & 1) > 0) cache.add(S[index]);
                tmp = tmp >> 1;
                index++;
            }
            result.add(cache);
        }
        return result;
    }
}