28. Subsets (Power Set)

Difficulty:MediumPattern:Backtracking / Decision TreeTime:O(n * 2^n)Space:O(n)

Given an integer array nums of unique elements, return all possible subsets (the power set).

How It Works & Algorithmic Design

Solves using Backtracking / Decision Tree Search:

Decision Tree: At each element index start, decide to either include nums[start] in the current subset or exclude it.
Backtracking Function backtrack(start, currentPath):
- Save copy of currentPath into result.
- Loop $i$ from start to nums.length - 1:
  - Include: currentPath.push(nums[i]).
  - Recurse: backtrack(i + 1, currentPath).
  - Backtrack: currentPath.pop().

Why This Approach Works Best

An array of size $n$ has $2^n$ unique subsets. Backtracking generates all combinations systematically in $O(n \cdot 2^n)$ time and $O(n)$ call-stack space.

Example Walkthrough

Input: [1, 2, 3]

3 distinct numbers.

Output Set Count: 2^3 = 8 subsets

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

Answer: Power set generation using Backtracking

function subsets(nums) {
  const res = [];
  function backtrack(start, path) {
    res.push([...path]);
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);
      backtrack(i + 1, path);
      path.pop();
    }
  }
  backtrack(0, []);
  return res;
}

💡 Systematically explore subset inclusions and exclusions using recursive backtracking.

Key Takeaways

Backtracking builds solution state incrementally.
Power set size is always $2^n$ for $n$ distinct elements.
Always copy state ([...path]) before storing in result.