Subsets

The problem

Given distinct integers nums, return all possible subsets (the power set). No duplicate subsets. Order does not matter.

Input:  nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Brute force

Start from [[]]; for each num, duplicate all existing subsets and append num. Cascading build:

function subsetsCascade(nums: number[]): number[][] {
  const res: number[][] = [[]];
  for (const num of nums) {
    const n = res.length;
    for (let i = 0; i < n; i++) {
      res.push([...res[i], num]);
    }
  }
  return res;
}

This is optimal O(n·2ⁿ). Backtracking is the other standard form.

Optimal: backtracking

function subsets(nums: number[]): number[][] {
  const res: number[][] = [];
  const path: number[] = [];

  function dfs(start: number): void {
    res.push([...path]);
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);
      dfs(i + 1);
      path.pop();
    }
  }

  dfs(0);
  return res;
}

Bit mask

function subsetsBits(nums: number[]): number[][] {
  const n = nums.length;
  const res: number[][] = [];
  for (let mask = 0; mask < 1 << n; mask++) {
    const cur: number[] = [];
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) cur.push(nums[i]);
    }
    res.push(cur);
  }
  return res;
}

Time	O(n · 2ⁿ)
Space	O(n) aux + output

Edge cases

• Empty nums → [[]]
• Single element
• n ≤ 10 typical

Common bugs

• dfs(i) instead of dfs(i+1) → infinite / duplicates
• Not copying path into res
• Subsets II: forgetting sort + skip duplicates

Interview delivery

1. Power set size 2ⁿ.
2. Backtrack or cascade.
3. Show code.
4. Complexity.
5. Follow-up subsets with duplicates.

Related

• Permutations
• Combination Sum
• Palindrome Partitioning
• Letter Combinations Phone Number

Worked include/exclude tree

For [1,2]:

dfs(0) path=[]
  take 1 → dfs(1) path=[1]
    take 2 → dfs(2) path=[1,2] → record
    skip after pop
  skip 1 → dfs(1) path=[]
    take 2 → path=[2] → record

Records also fire at every node entry, so [] and [1] appear without needing a separate “skip only” branch style. The start-index loop and the pure include/exclude recursion generate the same power set.

When interviewers switch constraints

• Subsets II (duplicates): sort, then skip nums[i] == nums[i-1] at the same depth.
• Size-k only: stop expanding when path.length == k (combinations).
• Sum constraints: add pruning when partial sum exceeds target.

Saying “this is the same skeleton as combinations with different base cases” scores well.

Complexity intuition out loud

There are exactly 2^n subsets. You spend O(n) work copying a path when recording (or O(1) if you only count). So Θ(n·2^n) is tight, not a loose upper bound. Bit masks make that obvious: 1 << n iterations, each scanning n bits.

Further reading

• LeetCode 78 — Subsets
• Power set