• 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

This is the first problem in the backtracking section, and it is the right place to build the technique from nothing — because the structure here is as simple as it ever gets, which makes the machinery visible.

Look at what defines a subset. For each element you make one decision: take it, or leave it. Nothing else. The subset is entirely determined by those decisions.

That immediately tells you how many subsets exist. Three elements means three independent yes-or-no decisions, and independent binary choices multiply: 2 × 2 × 2 = 8. In general 2ⁿ.

It also tells you the output is exponential, so no clever algorithm will make this fast. The work is unavoidable — you are being asked to produce 2ⁿ things. The only question is how to generate them systematically, without missing any and without producing any twice.

Draw the decisions as a tree. Start at the root with nothing chosen. The first branching is over element 0: one branch takes it, the other skips it. From each of those, branch on element 1. Then element 2.

After n levels of branching, every path from root to leaf has made a decision about every element — so each leaf is exactly one subset, and there are 2ⁿ leaves. Generating all subsets means walking every root-to-leaf path.

That reframing is the important move, and it is worth stating in general terms because every problem in this section uses it: a problem asking for "all possible X" is a problem about walking a tree of decisions, where each level is one decision and each leaf is one complete answer.

The obvious way to walk it is recursion. At each node you know which element you are deciding about and what you have chosen so far.

The naive implementation passes a fresh copy of the current subset down each branch:

def build(i, path):
    if i == len(nums):
        result.append(path)
        return
    build(i + 1, path + [nums[i]])    # take it — makes a new list
    build(i + 1, path)                # skip it

That works and is genuinely fine here. But it allocates a new list at every node of the tree, and the pattern does not survive into harder problems where the state being carried is large — a chessboard, a Sudoku grid, a marked-up input.

So the standard technique keeps one shared path and mutates it. Before recursing down a branch, modify the path to reflect that choice. After the recursion returns, undo the modification so the path is exactly as it was before, ready for the next branch.

def subsets(nums):
    result = []
    path = []

    def build(i):
        if i == len(nums):
            result.append(list(path))     # snapshot: copy, do not append path itself
            return

        path.append(nums[i])              # CHOOSE: take element i
        build(i + 1)                      # EXPLORE
        path.pop()                        # UN-CHOOSE: restore the shared state

        build(i + 1)                      # EXPLORE the skip branch

    build(0)
    return result

That three-beat rhythm — choose, explore, un-choose — is the entire pattern, and every remaining problem in this section is a variation on it. The name backtracking refers to the third beat: you back out of a decision to try a different one.

It is worth being explicit about this, because it looks like bookkeeping and it is not.

The shared path represents the decisions made on the route from the root to where you are now. When recursion returns from a branch, you are conceptually back at the parent node — so the path must again describe the parent's state. If the child's modification is left in place, the sibling branch inherits a decision it never made, and every subset generated beneath it is wrong.

So the invariant is: when a call returns, the shared state is exactly as it was when the call began. Every backtracking function must preserve it, and every bug in this section comes from breaking it.

Tracing every call, with the path shown at each point:

Result: [[1,2], [1], [2], []]. Four subsets for two elements, and note the path is [] again at the end — the invariant held all the way back to the root.

There is a much shorter solution, and it is the one to mention if asked for another approach.

Start with a list containing only the empty subset. For each element, take every subset already built and produce a copy with the element added.

def subsets(nums):
    result = [[]]
    for num in nums:
        result += [curr + [num] for curr in result]
    return result

Same complexity, three lines. It is a direct transcription of the counting argument: each new element doubles the answer, because every existing subset either takes it or does not.

There is also a bit-manipulation version — the numbers 0 to 2ⁿ-1 each encode one subset, with bit i deciding element i — which is the most literal expression of "n independent binary choices" and worth a sentence in an interview.

So why learn the backtracking form for a problem with a three-line solution? Because the doubling trick is specific to this problem, and the choose-explore-un-choose skeleton is not. Combinations adds a constraint on which choices are available. Permutations changes what counts as a choice. Combination Sum allows reuse and prunes on a running total. N-Queens and Sudoku prune on constraints at every level. All of them are this same function with different slots filled.

Train the reflex: when a problem asks for all of something, define one decision, define the choices available at each decision, and walk the tree — choosing, exploring, and always undoing on the way back out.