Problem Statement

Subsets

You are given an array of numbers called nums, and every number in it is different (no repeats). Your job is to return every possible subset. A subset is any group you can make by picking some of the numbers, including picking none of them and picking all of them. The full collection of all subsets is called the power set. None of the subsets should be the same, and you can return them in any order.

mediumBacktrackingBacktrackingTime: O(n * 2^n) · Space: O(n)

Signals to notice

generate all subsetsinclude or exclude each elementpower set

Brute force first

Not applicable — generating all subsets IS the problem. There's no shortcut because the output is 2^n subsets. That instinct is useful because it follows the prompt literally, but it usually keeps revisiting work the problem is begging you to organize.

The key insight

Backtracking: for each element, choose to include or exclude it. Build subsets incrementally. — unavoidable because that's the output size. Instead of recomputing the world every time, you preserve just enough context to let the next decision become obvious.

Trace it on `nums=[1,2,3]`

bt(0,[]): record [] -> result=[[]]
i=0: push 1 -> bt(1,[1]): record [1] -> result=[[],[1]]
i=1: push 2 -> bt(2,[1,2]): record [1,2]; i=2: push 3 -> bt(3,[1,2,3]): record [1,2,3]; pop 3; pop 2
back at bt(1): i=2: push 3 -> bt(3,[1,3]): record [1,3]; pop 3; pop 1
i=1: push 2 -> bt(2,[2]): record [2]; i=2: push 3 -> bt(3,[2,3]): record [2,3]; pop 3; pop 2
i=2: push 3 -> bt(3,[3]): record [3]; pop 3
return result=[[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]

What must stay true

At each position, you make a binary choice: include the current element or skip it. Exploring all combinations of these choices generates every subset exactly once. As long as that statement keeps holding, you can trust the steps built on top of it.

Shape of the loop

function backtrack(start, current):
    result.append(copy(current))      # every node is a valid subset
    for i from start to n-1:
        current.append(nums[i])       # choose i
        backtrack(i + 1, current)     # recurse on remaining
        current.pop()                 # undo choice

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Generating duplicates — process elements in order and only add elements at or after the current index to avoid permutations of the same subset. The fix is usually to return to the meaning of each move, not just the steps themselves.

Backtracking Pattern