Subsets

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

Note: The solution set must not contain duplicate subsets.

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

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

A very old question, basically we use backtracking to solve it. However, besides normal recursive solution, we can use iteration to solve the problem. The idea behinds it is that for every number in the array, we add it to every existing subset and add the new subset back to result. It takes the same O(2^n) complexity.

public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> rst = new ArrayList<>();
        rst.add(new ArrayList<Integer>());
        for (int i = 0; i < nums.length; i++) {
            int size = rst.size();
            for (int j = 0; j < size; j++) {
                List<Integer> newSet = new ArrayList<>(rst.get(j));
                newSet.add(nums[i]);
                rst.add(newSet);
            }
        }
        return rst;
    }