Question

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],
  []
]

Solution

• This discussion is very helpful in understanding the general pattern to solve this problem.
• It is very important to understand the recursive call for this solution and how the recursion unwinds.

The time complexity of the above approach is hard to analyze. Another way to solve this problem which is easier to understand and analyze is below.

• The general idea can can be found in Chapter 5 of Competitive Programmer's Handbook

void search(int k) {
    if (k == n) {
        // process subset
    } else {
        search(k+1);
        subset.push_back(k);
        search(k+1);
        subset.pop_back();
    }
}

Time complexity

Space complexity

O (n) which is the space taken by the stack to keep track. Also the solution uses recursion so it does take some space on call stack.

Notes