FAANGPrep Sprint

Subsets (Power Set)

Generate every subset of distinct numbers by deciding each one in turn: leave it out, take it, undo.

MediumSolve on LeetCode

Examples

Input:nums = [1,2,3]

Output:[[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]

Explain:

Eight subsets. Leaving out before taking returns them as a binary count; any order is accepted.

Input:nums = [0]

Output:[[],[0]]

Explain:

One decision: leave 0 out, then take it.

Problem Understanding

The integer array nums holds distinct values. Return every subset of them, from the empty set up to the whole array: the power set.

Example: nums = [1, 2, 3]

Output: [], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]

There are 2ⁿ of them: each number is either in a subset or out of it.

Algorithm Strategy

Each number is either in a subset or out of it, and the choices are independent — so n numbers give 2ⁿ subsets.

backtrack(i) makes the decision for nums[i]:

Leave it out — recurse on i + 1 with the path unchanged.
Take it — append nums[i], recurse on i + 1.
Undo — pop it, so the call hands its caller back the path it was given.

When i reaches n every number has been decided, so the path is a finished subset: copy it into the result and return.

Leaving out before taking means the undo comes last, right before the call returns — and it makes the answer come out in a fixed order: read each subset as in/out marks over nums, and the result counts upward in binary.

Interactive Visualization

DEPTH = THE NUMBER BEING DECIDED · A DOT LEFT IT OUT, A NUMBER TOOK IT · BELOW A NODE: THE SUBSET SO FAR

EMPTY RESULT AND PATH

deciding

—

recorded

0/8

Answer

—

decisions (in / out / open)

1 ?

2 ?

3 ?

result

Nothing recorded yet

Start with an empty result and an empty path. 3 numbers, so 8 subsets to find

Leave 1 out: call backtrack(1) with the path still []

nums

Legend & Complexity

The call running now

Waiting for a deeper call to return, or the call about to be made

A recorded subset: every number decided

Returned — both branches under it are done

Time

O(n × 2ⁿ)

Space

O(n) depth, O(n × 2ⁿ) output

Every node is one call to backtrack(i); its depth is the number it is deciding. A call's left child left that number out and is drawn as a dot; its right child took it and is labelled with it. The line under a node is the subset that call holds.

Only the bottom row records, so the result beside the figure fills in left to right. The decision row beside it shows each number as in, out or ? — that row is the state of the recursion. Try Negatives: the values never change the shape, only the positions do.

Dry Run

Tracing nums = [1, 2] all the way through.

#	Call	Path	What happens
1	`backtrack(0)`	`[]`	Leave 1 out → `backtrack(1)`
2	`backtrack(1)`	`[]`	Leave 2 out → `backtrack(2)`
3	`backtrack(2)`	`[]`	All decided: record `[]`, return
4	`backtrack(1)`	`[2]`	Take 2 → `backtrack(2)`
5	`backtrack(2)`	`[2]`	Record `[2]`, return
6	`backtrack(1)`	`[]`	Pop 2 — return
7	`backtrack(0)`	`[1]`	Take 1 → `backtrack(1)`
8	`backtrack(1)`	`[1]`	Leave 2 out → `backtrack(2)`
9	`backtrack(2)`	`[1]`	Record `[1]`, return
10	`backtrack(1)`	`[1, 2]`	Take 2 → `backtrack(2)`
11	`backtrack(2)`	`[1, 2]`	Record `[1, 2]`, return
12	`backtrack(1)`	`[1]`	Pop 2 — return
13	`backtrack(0)`	`[]`	Pop 1 — return

Result: [[], [2], [1], [1, 2]] — as in/out marks over [1, 2] that is 00, 01, 10, 11.

Edge Cases & Common Mistakes

Watch out for these pitfalls:

Empty Input: nums = [] should return [[]], not [].
Duplicate Elements: This specific problem assumes unique elements. If duplicates were allowed (Subsets II), you would need to sort and skip duplicates to avoid generating the same subset twice.
Reference Trap: A very common bug in Java/Python is adding the current list reference to result. Since current keeps changing, your final result will be a list of empty lists. Always use new ArrayList<>(current) or subset.copy().

Solution

One algorithm in all six languages — the lines light up as the figure above steps.

Subsets (Power Set) Code

1var subsets = function(nums) {
2    const result = [];
3    const path = [];
4
5    const backtrack = (i) => {
6        if (i === nums.length) {
7            result.push([...path]);
8            return;
9        }
10        backtrack(i + 1);
11        path.push(nums[i]);
12        backtrack(i + 1);
13        path.pop();
14    };
15
16    backtrack(0);
17    return result;
18};