Algorithm

Subsets (Power Set)

Backtracking Pattern

Subsets

Given an array of distinct integers, return every possible subset — the power set.

A subset is formed by choosing, independently for each element, whether to include it. That includes taking none of them (the empty subset) and taking all of them, both of which must appear in the output.

Subsets are sets, so order within a subset carries no meaning and no subset may be listed twice. The order of the subsets themselves does not matter.

CONSTRAINTS
  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • All integers in nums are distinct
  • The output contains exactly 2ⁿ subsets, including the empty one
  • Subsets may be returned in any order
EXAMPLE 1
Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Eight subsets for three elements — one for every combination of independent include-or-exclude decisions. Note that [1,2] appears but [2,1] does not: they describe the same set, so only one representative is listed.
EXAMPLE 2
Input: nums = [0]
Output: [[],[0]]
A single element yields two subsets: the one omitting it and the one taking it. The empty subset is a genuine answer, not an edge case to skip — leaving it out is the most common mistake here.
EXAMPLE 3
Input: nums = [1,2]
Output: [[],[1],[2],[1,2]]
Two elements give four subsets. Each additional element doubles the count, since every existing subset can either take the newcomer or not — which is exactly why the total is a power of two.
EXAMPLE 4
Input: nums = [-1,5]
Output: [[],[-1],[5],[-1,5]]
Values are irrelevant to the structure of the answer. Negatives, zero and duplicat-free ordering change nothing: only the positions matter, because each element is independently taken or not.
Should the empty subset be included?
Yes. Excluding every element is a legitimate set of choices, and the power set of any collection always contains it. An output of size 2ⁿ is only achievable with it present.
Are the input elements guaranteed distinct?
Here, yes, and it matters enormously. With duplicates, [2,2] would produce identical subsets by different routes and you would need to sort the input and skip repeated values at each level — that variant is Subsets II.
Does the order of elements within a subset matter, or the order of subsets in the output?
Neither. [1,2] and [2,1] are the same subset and only one should appear. The subsets themselves may be returned in any order, which means no sorting step is required at the end.
How large can the output get?
2ⁿ subsets, which at n = 10 is 1024. That the answer itself is exponential is worth saying out loud: no algorithm can beat exponential time here, because merely writing the output takes that long.

A subset is one yes/no decision per element: take it, or leave it. Make those decisions one element at a time, and every full set of decisions is one subset. That's a tree — n levels deep, 2ⁿ leaves, one subset per leaf. Generating all subsets means walking every path to the bottom.

The backtracking template

Every problem in this section is the same loop — three beats: choose, explore, un-choose.

python
def backtrack(state):
    if done(state):
        save(state)              # record the finished answer
        return
    for choice in choices(state):    # what can I pick right now?
        if not ok(choice):
            continue                 # prune: skip bad picks early
        apply(choice)                # CHOOSE
        backtrack(next_state)        # EXPLORE
        undo(choice)                 # UN-CHOOSE: put it back

Only four slots change between problems: done, choices, ok (pruning), and how you finish (save every answer, or return True at the first one). Fill those and the problem is solved.

What changes here
- A choice = take element i, or skip it.
- Choices = the two branches at index i.
- Done = walked past the last element (i == n) → save the path.
- Prune = nothing; every path is a valid subset.
python
def subsets(nums):
    res, path = [], []

    def backtrack(i):
        if i == len(nums):
            res.append(list(path))    # save a COPY, not path itself
            return
        path.append(nums[i])          # CHOOSE: take it
        backtrack(i + 1)              # EXPLORE
        path.pop()                    # UN-CHOOSE
        backtrack(i + 1)              # EXPLORE: skip it

    backtrack(0)
    return res

Two things bite everyone: save list(path) (a copy) — appending path stores a reference that keeps changing. And the pop() goes between the two calls, so the skip branch starts clean.

Trace [1,2]: take 1 → take 2 → save [1,2]; drop 2 → save [1]; drop 1 → take 2 → save [2]; drop 2 → save []. Result [[1,2],[1],[2],[]].

Interactive Strategy Visualization

The Recursion Tree

Visualizing how the algorithm branches for each decision.

Root[]+1-1+2-2+2-2
Active Path
Found Subset
Start at the Root (Empty Set). We have 2 choices for number '1'.
TREE STRUCTURE

The tree grows from left to right. Each level corresponds to one number in the input. For each number, we branch Up (+ Include) or Down (- Exclude).

DFS TRAVERSAL

Backtracking is simply a Depth First Search. We go as deep as possible into one reality, then step back to the last fork and try the other path.

O(N × 2ⁿ) Enumerate All Binary Masks
→
O(N × 2ⁿ) Iterative Doubling
→
O(N × 2ⁿ) Backtracking With O(N) Working Space