78. Subsets — DSA Atlas

MediumBacktrackingBacktracking (DFS over a decision tree)Subset enumeration by include/exclude

Subsets

Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets, and the subsets may be returned in any order.

Open official problem prompt ↗

In plain English

Produce the power set: every possible selection of elements, from the empty set up to the whole array.

Picture it like this

Picture packing for a trip with 3 items on the table. For each item you make one yes/no decision; the set of all decision paths is exactly the set of all possible bags you could pack.

Example

Input: nums = [1, 2, 3]
Output: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]
Why: Every combination of choosing or skipping each of the 3 elements yields 2^3 = 8 distinct subsets.

Constraints

1 <= nums.length <= 10-10 <= nums[i] <= 10All the numbers of nums are unique

Pattern lesson

See the pattern, then code

Subset enumeration by include/exclude

↗

Backtracking

Generate every valid combination, permutation, partition, or configuration.. Each element is an independent binary choice: include it or not. Walking that decision tree with a start index guarantees every subset is generated exactly once and in non-decreasing index order, so no duplicates arise.

New words, made simpleKnow these before the algorithm

Power set: The collection of all subsets of a set, including the empty set and the set itself; a size-n set has 2^n subsets.
Backtracking: Depth-first search that makes a choice, recurses, then undoes the choice to try alternatives.
Start index: The lowest index the current branch is still allowed to pick from, which prevents revisiting earlier elements and thus prevents duplicate subsets.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Cascading / iterative build-up

Correct and clean, but the extra copying of the whole result list each step is easy to get subtly wrong and less illustrative of the decision-tree pattern.

Start with [[]] and for each number append copies of every existing subset with the number added.

Time O(n * 2^n)Space O(n * 2^n)

Best choiceBacktracking with start index

Canonical, memory-light (only recursion stack beyond the output), and the template generalizes directly to combinations and permutations.

DFS that records the current path at every node and iterates remaining indices, choosing and un-choosing each.

Time O(n * 2^n)Space O(n)

The rule we keep true

Invariant

At any call with a given start index, path holds a valid subset built only from indices strictly less than start, and every subset that extends path using indices >= start will be emitted exactly once.

Why this is correct

Reasoning

Because recursion always advances start to i + 1, no index is ever reused within a branch and elements are only added in increasing index order. Every subset corresponds to exactly one increasing sequence of indices, so each is generated once and none is missed.

The algorithm in three movesSay these aloud before coding

1Record the current path as a subset at the top of every call

path = [1] -> record [1]

2Loop i from a start index to the end of nums

path = [1,2] -> record [1,2]

3Choose nums[i], recurse with start = i + 1, then un-choose (pop) to explore the sibling

path = [1,2,3] -> record [1,2,3]

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readstart = 0

2 · AskRecord current path?

3 · Update statepath = []

4 · ResultEmit []

Key takeaway

The decision tree branches on include/skip for each index; every node emits one subset.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 5-6State containers
res collects finished subsets; path is the mutable current selection shared across the recursion.
2
Lines 8-9Emit every node
A copy of path is recorded at the start of each call, so partial paths (including the empty one) all count as subsets.
3
Lines 10-13Choose / recurse / un-choose
Append nums[i], dive with start = i + 1 to avoid earlier indices, then pop to restore state for the next sibling.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Single element [x] returns [[], [x]]
Negative values are fine since we never compare magnitudes
The empty subset is always present because we record before the loop

Common beginner mistakes

Appending path directly instead of path[:] stores a reference that later mutations corrupt
Recursing with start = start + 1 instead of i + 1, which drops valid subsets
Forgetting to pop after recursion, leaking elements into sibling branches

Check your understanding

Why does using a start index eliminate duplicate subsets even though nums has no duplicates?

Subsets

Subsets

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Backtracking