The Backtracking Template

Every backtracking problem fits the same skeleton. Once you can write the skeleton from memory, the work on any new problem is filling in three blanks:

What’s a “complete” partial solution? (When do we record an answer?)
What are the candidate choices at each step?
Which candidates are legal? (The pruning predicate.)

That’s it. Internalize the skeleton and you’ll never have to re-derive how to enumerate things from scratch.

The skeleton

def backtrack(state):
    if is_complete(state):
        record(state)
        return
    for choice in candidates(state):
        if is_legal(choice, state):
            apply(choice, state)            # choose
            backtrack(state)                # recurse
            undo(choice, state)             # un-choose

Four lines do the work. The “choose → recurse → un-choose” sandwich is the heart of the algorithm. Skipping the undo is the single most common backtracking bug — you’ll leak state from one branch into the next and get phantom answers.

⚠️

The “snapshot” rule. When you record a solution at a leaf, you must record a copy of path, not a reference to it. The same path object will be mutated on the next iteration — if you stored a reference, all your “saved” answers will end up identical. In Python: out.append(path[:]). In Java: new ArrayList<>(path). In C++ the assignment out.push_back(path) already copies a vector<int>.

Four canonical shapes

These four templates cover the majority of enumeration problems. Memorize the structure of each, and notice the tiny differences between them — that’s where the interview gotchas live.

Shape 1 — Subsets (2^n)

Given nums, generate all subsets.

At each index, choose to include or skip.

Time: O(2^n × n). The tree has 2^n leaves; each costs O(n) to record.

Alternative “iterate-over-remaining” form

There’s a second way to enumerate subsets that’s slightly cleaner for many follow-ups (subsets with duplicates, k-sized combinations, etc.):

def subsets(nums):
    out, path = [], []
    def bt(start):
        out.append(path[:])                   # every prefix IS a subset
        for i in range(start, len(nums)):
            path.append(nums[i])
            bt(i + 1)
            path.pop()
    bt(0)
    return out

Here every node of the recursion tree is itself a subset (not just the leaves), and the loop generates “next element to add” rather than “include/skip the current element.” Same 2^n count of subsets, different tree shape. Both styles are correct; pick the one whose pruning is easier for the specific problem.

Shape 2 — Permutations (n!)

Given distinct nums, generate all orderings.

At each step, pick the next unused element. Track usage with a used[] boolean array.

Time: O(n! × n). There are n! permutations; each costs O(n) to copy.

In-place swap variant

You can also generate permutations by swapping in place, no used array:

def permute(nums):
    out = []
    def bt(start):
        if start == len(nums):
            out.append(nums[:])
            return
        for i in range(start, len(nums)):
            nums[start], nums[i] = nums[i], nums[start]
            bt(start + 1)
            nums[start], nums[i] = nums[i], nums[start]      # undo swap
    bt(0)
    return out

O(1) extra space (besides the output). The trade-off: handling duplicates is harder — you’d need an explicit “have we already tried this value at this position?” set per recursive call.

Shape 3 — Combinations (C(n, k))

Given n and k, return all k-sized subsets of [1..n].

A subset enumerator with two stopping conditions: stop at k picks (success) or when we’ve run out (fail). Use the “iterate-over-remaining” form because we need a start index to enforce ordering.

Time: O(C(n, k) × k).

The n - need + 1 upper bound is a free pruning win: if we’d need 3 more numbers and there are only 2 left, don’t even start the iteration.

Shape 4 — Partitions

Given a string, partition it into pieces (each piece satisfying some property).

At each step, choose where the next cut goes. The candidates are “cut after position i” for i in [start + 1 .. n].

This is the shape behind Palindrome Partitioning, Restore IP Addresses, Word Break II, and most “split a string into valid pieces” problems. The candidate generator (where to cut) and validator (is the piece OK?) are the only problem-specific parts.

The recipe — putting it all together

When you see a new problem and suspect backtracking, run this:

Pick a template

Subsets? Permutations? Combinations? Partitions? Grid DFS (next page)? Constraint placement (next page)? There are five of them; one of them fits.

Define the state

Usually path (the current partial solution) plus an index/start/used-array to know what’s still available.

Write the base case

When is path a complete solution? When do we record it?

Write the candidate loop

What are the choices at this step?

Write the legality check

When is a candidate allowed? This is the pruning — even a cheap O(1) check (no duplicates, in bounds, doesn’t break a constraint) is enough to cut the search by orders of magnitude.

Write the undo

Whatever apply(choice) did, undo(choice) reverses it. Forget this and your branches will leak.

If the template is wrong, the answers are wrong. If the template is right, the rest is mechanical.

A summary table

Shape	Tree size	Choice at each step	Stopping condition
Subsets	`2^n` leaves	Include / skip `nums[i]`	`i == n`
Permutations	`n!` leaves	Pick next unused element	`path.length == n`
Combinations	`C(n, k)`	Pick next ordered element	`path.length == k`
Partitions	varies	Pick a cut position	`start == n`
Grid DFS	up to `4^(r×c)`	Move in one of 4 directions	Target found / bounds hit
Constraint placement	varies	Pick a value at this slot	All slots filled / no candidate left

The last two shapes get their own page (next: pruning, then advanced).

Quick check

In the recursion `path.append(x); bt(); path.pop()`, what happens if you forget the `path.pop()`?

Why is the 'iterate over remaining' subset variant often preferred for combinations and combination-sum problems?

You're enumerating permutations and the output looks correct, but the SAME permutation appears twice. What's the likely cause?

Next: pruning — the single highest-leverage thing you can do to take a TLE-ing backtracking solution to a sub-millisecond one.

Introduction Pruning