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

Note:

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

Example

For set = [1, 2, 3], subsets are:

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

Using bit manipulation.

class Solution {
    /**
     * @param S: A set of numbers.
     * @return: A list of lists. All valid subsets.
     */
    public ArrayList<ArrayList<Integer>> subsets(int[] nums) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        int stop = (int)Math.pow(2, nums.length);
        for (int bitmap = 0; bitmap < stop; bitmap++) {
            ArrayList<Integer> set = new ArrayList<>();
            int mask = 1, j = 0;
            while (mask < stop) {
                if ((bitmap & mask) != 0)
                    set.add(nums[j]);
                mask <<= 1;
                j++;
            }
            Collections.sort(set);
            res.add(set);
        }
        return res;
    }
}