Subsets

MediumBacktrackingArrayBacktrackingBit Manipulation

Problem

Given an array of distinct integers, return every possible subset of it, including the empty set and the full array itself. The output should contain each subset exactly once; order among subsets, and within a subset, does not matter.

Example. For [1, 2, 3], the output is [], [1], [2], [3], [1,2], [1,3], [2,3], and [1,2,3]: eight subsets in total.

Key idea

Since each of the n elements is either in a subset or not, there are 2^n subsets to produce, and any correct method must do at least that much work. The natural way to generate them is a decision tree: process elements one at a time, branching at each into two choices, include it or leave it out.

Walk the array with a recursive helper carrying a partial subset. At each index, record the current partial subset as one output, then recurse twice: once having pushed the current element on, and once having left it out, undoing the push before the second call (backtracking) so the shared structure is correct for the sibling branch. Reaching the end of the array closes off both branches. Equivalently, since each subset corresponds to a unique n-bit binary number, walking every integer from 0 to 2^n - 1 and reading off its bits produces the same enumeration without recursion.

Solution

function subsets(nums: number[]): number[][] {
  const result: number[][] = [];
  const partial: number[] = [];

  function backtrack(index: number): void {
    if (index === nums.length) {
      // Every element has been decided in or out; record this subset.
      result.push([...partial]);
      return;
    }

    // Include nums[index].
    partial.push(nums[index]);
    backtrack(index + 1);
    partial.pop();

    // Exclude nums[index].
    backtrack(index + 1);
  }

  backtrack(0);
  return result;
}

Complexity

  • Time: O(n · 2ⁿ). 2ⁿ subsets, each costing O(n) to copy into the output.
  • Space: O(n). Recursion depth and the partial subset, excluding the output.

Watch out for

  • Copy the partial subset when recording it; storing a reference to the mutable working list means every recorded subset reflects only its final, empty state.
  • Don't skip the empty subset; it's a valid output, not an edge case to special-case away.

Pattern

This is the template backtracking problem for the include/exclude decision tree, used whenever a problem asks for every combination of a set rather than a single valid one. Subsets II and the Combination Sum family build on this same skeleton with extra pruning layered on top.

Related questions