Subsets

Generate a power set through an include-or-exclude decision tree

Make one binary decision per element

Every subset of an n-element set is determined by n decisions: include the next element or exclude it. Those choices form a complete binary tree of depth n, with one subset at each of its 2^n leaves.

Traverse the decision tree depth first

Follow the include branch, recurse, undo that choice, then follow the exclude branch. The highlighted root-to-node path is the current recursion stack. Reaching a leaf means every element has a decision, so the current subset can be recorded.

The player expands all choices for [1, 2, 3]. Visited nodes remain visible, green leaves are recorded subsets, and the edge labels make every include or exclude operation explicit.

Start at the empty set and decide whether to include each element in order.

1function subsets(nums: number[]): number[][] {
const res: number[][] = [];
const cur: number[] = [];
const backtrack = (i: number): void => {
  if (i === nums.length) {
    res.push([...cur]);
    return;
  }
  cur.push(nums[i]);       // include nums[i]
  backtrack(i + 1);
  cur.pop();               // undo (backtrack)
  backtrack(i + 1);        // exclude nums[i]
};
backtrack(0);
return res;
16}

Elements1 2 3

Current subset∅

Recorded0 / 8

1 / 31

Output size sets the lower bound

There are 2^n subsets. Materializing each result may copy up to n values, so the total time and output space are O(n * 2^n). The active recursion path itself uses only O(n) space.

Invariant: each root-to-leaf path assigns one distinct include/exclude bit to every element, so the traversal produces every subset exactly once.

Add constraints and pruning to the same decision-tree model in N-Queens.

Algorithm Visualizer

Subsets

Make one binary decision per element

Traverse the decision tree depth first

Output size sets the lower bound