Backtracking

Look at the input size before you look at anything else. Backtracking explores an exponential space — 2^n subsets, n! permutations — so it's only viable when n is tiny.

2^20 ≈ 10^6 — comfortably fast. 2^40 is a trillion — dead. So when you see nums.length <= 20, or "return all subsets / permutations / combinations / valid boards", the interviewer is telling you to enumerate exhaustively. The skill being tested isn't cleverness; it's whether you can enumerate without missing anything and without repeating anything.

Tell: the word "all" in the output ("return all…") plus a small n is the loudest backtracking signal in interviews.

Picture the search as a tree. The root is the empty partial solution. Each edge is one choice (include this number, place a queen in this column, cut the string here). Each leaf is a complete candidate.

nums = [1, 2]            []
                  include 1 /  \ skip 1
                        [1]    []
               include 2 / \    / \ include 2
                   [1,2] [1]  [2]  []

Backtracking is just depth-first search on this tree — except the tree is never built in memory. You walk it: descend by making a choice, and when you return, undo the choice so the shared path list is clean for the next branch.

Two questions design the whole tree:

1. What are the choices at this node? (which elements / positions / cuts are still legal)
2. When is a node a leaf? (the partial solution is complete — or provably hopeless)

Answer those two and the code writes itself.

Every backtracking solution you will ever write is this function wearing a different costume:

def solve(problem):
    results = []
    path = []                          # the partial solution, shared & mutated

    def backtrack(state):
        if is_complete(state):         # leaf: record a snapshot
            results.append(path[:])    # copy! path keeps mutating after this
            return
        for choice in legal_choices(state):
            path.append(choice)        # 1. CHOOSE
            backtrack(next_state)      # 2. EXPLORE
            path.pop()                 # 3. UN-CHOOSE — restore exactly

    backtrack(initial_state)
    return results

Three rules that prevent 90% of bugs:

• Snapshot at the leaf. results.append(path) stores a reference to a list you're about to mutate — every result ends up empty. Always path[:] or list(path).
• Undo must mirror do. Whatever append/mark/set you did before recursing, reverse it after — exactly once, unconditionally.
• Pass the frontier, not the history. A start index (combinations) or a used set (permutations) tells each node which choices remain. start enforces "only look rightwards," which is what kills duplicate orderings of the same combination.

Raw backtracking visits every node. Pruning chops entire subtrees the moment a partial solution becomes impossible — and it's the difference between "times out" and "instant."

def backtrack(start, remaining):
    if remaining == 0:
        results.append(path[:]); return
    for i in range(start, len(candidates)):
        if candidates[i] > remaining:   # sorted input ⇒ everything after
            break                       # is bigger too: prune the rest
        path.append(candidates[i])
        backtrack(i, remaining - candidates[i])
        path.pop()

The classic pruning moves:

• Sort first, then break when a candidate overshoots — every later candidate overshoots too.
• Check constraints on the way down, not at the leaf. In N-Queens, test column and diagonal conflicts before placing — don't build a full board and validate it at the end.
• Skip duplicate branches: with sorted input, if i > start and nums[i] == nums[i-1]: continue ensures only the first copy of a value starts a branch at each tree level. Same subtree, explored once.

Say the word "prune" in the interview. Naming the optimization is worth as much as coding it.

The template has four slots. Filling them is solving the problem:

Notice the complexity is the size of the output times the cost per leaf — O(n · 2^n) for subsets, O(n · n!) for permutations. You can't beat the output size; when asked "can you do better?", that's the answer.

Interview script: state the choices, state the leaf, write the skeleton, then ask yourself "what branches can I prove dead early?" — out loud.