Backtracking

On this page

The Idea
Build It
Know It
Break It
Use It

Quick reference

subsets(nums), n elements	O(2ⁿ)
permutations(nums), n elements	O(n!)
combinations(n, k)	O(C(n, k)) ≈ up to O(2ⁿ)
any backtracking search, generally	exponential or factorial

The Idea

Recursion Basics taught you to ask a smaller version of yourself to solve a smaller version of the problem. Backtracking is that same trick, plus one new move: try a choice, recurse as if it were correct, and if it turns out wrong — or you've explored everything reachable from it — undo the choice and try the next one. The undo is what's new. Plain recursion never takes anything back; backtracking does, on purpose, every single time.

Picture exploring a maze. At a fork you commit to a path and keep walking. If it dead-ends, you don't restart from the entrance — you walk back to the last fork and try a direction you haven't tried yet. That walk back is the backtrack: you're not giving up, you're returning to the most recent decision point with everything reset to how it looked before you made that choice, so the next attempt starts clean.

The reason this works at all is the same reason recursion works: the call stack remembers where you were. Each recursive call holds its own "which choice am I trying" state, so when a deeper call finishes — whether it succeeded or hit a dead end — control returns to exactly the point that made the choice, ready to try the next option.

Every backtracking function has the same three moves in the same order: choose (add an option to your partial solution), explore (recurse with that choice in place), un-choose (remove it before the next iteration tries a different option). Skipping the un-choose step is the single most common bug in this entire topic.

Build It

Shape of a backtracking function

function backtrack(partialSolution, choicesRemaining):
    if partialSolution is a complete answer:
        record a copy of partialSolution
        return
    for each option in choicesRemaining:
        partialSolution.add(option)              // choose
        backtrack(partialSolution, choicesRemaining - option)   // explore
        partialSolution.remove(option)            // un-choose — the actual backtrack

subsets — each element is in, or it's out

function subsets(nums):
    result = []
    current = []

    function backtrack(i):
        if i == len(nums):            // base case: decided every element
            result.add(copy of current)
            return
        current.add(nums[i])          // choose: include nums[i]
        backtrack(i + 1)              // explore
        current.remove(nums[i])       // un-choose

        // explore the "exclude nums[i]" branch — nothing to un-choose, we added nothing
        backtrack(i + 1)

    backtrack(0)
    return result

Two recursive calls per index, one for "in" and one for "out" — that's a binary choice repeated n times, which is exactly why the count of subsets is 2ⁿ.

permutations — choose which unused element goes next

function permutations(nums):
    result = []
    current = []
    used = array of false, size len(nums)

    function backtrack():
        if len(current) == len(nums):     // base case: placed every element
            result.add(copy of current)
            return
        for i in 0..len(nums):
            if used[i]:
                continue                   // already placed — not a legal choice right now
            used[i] = true                 // choose
            current.add(nums[i])
            backtrack()                    // explore
            current.remove(current.length - 1)  // un-choose
            used[i] = false                // un-choose

    backtrack()
    return result

Unlike subsets, every element is still a candidate at every position — the `used` array is what stops you from placing the same element twice in one permutation. First position has n choices, second has n-1, third has n-2 — that product is n!.

combinations — subsets with a fixed size, no repeats of the same group

function combinations(n, k):
    result = []
    current = []

    function backtrack(start):
        if len(current) == k:             // base case: picked enough elements
            result.add(copy of current)
            return
        for i in start..n:                 // only look forward from 'start'
            current.add(i)                 // choose
            backtrack(i + 1)               // explore — next call starts AFTER i
            current.remove(current.length - 1)  // un-choose

    backtrack(1)
    return result

The 'start' parameter is the whole trick: without it, [1,2] and [2,1] would both get generated as if they were different combinations, when a combination doesn't care about order. Forcing every recursive call to only pick indices at or after 'start' means each group of elements can only ever be built in one order — ascending.

pruning — cutting a branch before it's fully explored

function combinationSum(candidates, target):
    result = []
    current = []

    function backtrack(start, remaining):
        if remaining == 0:                 // base case: hit the target exactly
            result.add(copy of current)
            return
        if remaining < 0:                  // PRUNE: overshot, no point continuing
            return
        for i in start..len(candidates):
            current.add(candidates[i])              // choose
            backtrack(i, remaining - candidates[i])  // explore (i, not i+1 — reuse allowed)
            current.remove(current.length - 1)       // un-choose

    backtrack(0, target)
    return result

The `remaining < 0` check is a prune: it stops exploring a branch the instant it's provably dead, instead of walking all the way down to a base case that was never going to succeed. Without it, the function still gets the right answer eventually — it just does far more work getting there. Pruning doesn't change what backtracking can solve; it changes how much of the search tree you actually have to visit.

Know It

Backtracking explores a tree of choices, so its worst case is however big that tree is — no shortcut changes that, because there usually isn't a shortcut for these problems. What pruning buys you is a smaller tree in practice, not a smaller ceiling on paper.

Operation	Time	Space	Why
subsets(nums), n elements	O(2ⁿ)	O(n)	Two choices — include or exclude — repeated for each of n elements, so the recursion tree has 2ⁿ leaves. Space is just the recursion depth (at most n frames deep) plus the current partial subset, not the 2ⁿ output itself.
permutations(nums), n elements	O(n!)	O(n)	n choices for the first slot, n-1 for the second, and so on — that product is n!. Depth of the recursion (and the size of `current` and `used`) is still only O(n).
combinations(n, k)	O(C(n, k)) ≈ up to O(2ⁿ)	O(k)	Bounded by how many size-k groups exist; in the worst case (k around n/2) that's still exponential in n. The stack only ever holds the current partial combination, which never exceeds size k.
any backtracking search, generally	exponential or factorial	O(depth of recursion)	Same call-stack-cost lesson as Recursion Basics: the number of pending calls waiting on the stack at any instant is what space measures, and that's bounded by how deep one path through the choice tree goes — not by how many total paths exist.

Break It

Forgetting the un-choose step

a choice is added to the partial solution but never removed before the next iteration

This is the single most common backtracking bug. If `current.remove(...)` is missing (or runs before the recursive call instead of after), the partial solution silently keeps accumulating garbage from a branch you've already finished exploring — later branches see state left over from earlier ones instead of the clean slate they're supposed to get. The symptom is usually 'answers that look almost right, with extra or duplicated elements that don't belong.'

Duplicate input values without duplicate-skipping logic

the input has repeated values, e.g. [1, 1, 2]

Plain subsets/permutations code treats the two 1s as distinguishable because they sit at different indices, so it generates the same-looking answer twice — once for 'first 1 in, second 1 out' and once for the reverse, which look identical once printed. Fixing this needs an explicit rule, typically: sort the input first, then at each choice point skip an option if it's equal to the option immediately before it AND that previous option was skipped (not chosen) at this same level — otherwise the fix skips choices you actually needed.

Missing or wrong base case

the recursion never records a completed answer, or never stops

Same failure family as Recursion Basics: no base case (or one that's never reached) means the function recurses until it blows the call stack. A base case that's technically present but wrong — e.g. checking `i > len(nums)` instead of `i == len(nums)` — can silently skip recording valid complete answers, or record incomplete ones.

Skipping an obvious prune

a branch is provably dead but the code explores it anyway

A correct-but-unpruned combinationSum will still find every valid combination — it's not wrong, it's just slow, because it keeps recursing down branches where `remaining` already went negative instead of cutting them off immediately. Asymptotically the worst case doesn't change, but in practice the difference between pruning and not pruning is often the difference between finishing instantly and timing out.

Use It

Subsets

The choose/explore/un-choose template, verbatim: at each index, recurse once with the element included and once without.

Medium

Subsets II

Same as Subsets, but the input has duplicates — sort first, then skip an index if it equals the previous index and the previous one wasn't chosen at this level.

Medium

Permutations

The used-array template: at every position, try every not-yet-used element, mark it used, recurse, then unmark it.

Medium

Permutations II

Permutations with duplicate values — sort first, and at each position skip a value if it equals the previous value and the previous one is currently unused (meaning it was already fully explored and backtracked out).

Medium

Combinations

The start-index template, verbatim: recurse forward from `start`, stop once the partial combination reaches size k.

Medium

Combination Sum

Combinations plus a target-sum prune: pass `i` (not `i + 1`) to the recursive call since each number can be reused, and prune the instant the remaining target goes negative.

Medium

Combination Sum II

Combination Sum, but each number can only be used once and the input has duplicates — pass `i + 1` forward, sort first, and skip a value equal to the previous one at the same recursion level.

Medium

Letter Combinations of a Phone Number

Same shape as permutations of a fixed length: at digit index i, choose one of that digit's letters, recurse to digit i+1, un-choose.

Medium

Palindrome Partitioning

Start-index template again: at position `start`, try every cut point ahead of it, but only recurse into a cut whose substring is a palindrome — that palindrome check is the prune.

Medium

Generate Parentheses

Choose '(' or ')' at each step; prune any branch where close-count would exceed open-count, and only accept a complete answer once both counts equal n.

Medium

Word Search

Choose a direction to step from the current grid cell, explore, then un-choose by un-marking that cell as visited — the classic hard version of this idea is Sudoku Solver, which backtracks over a full 9x9 grid of constraints instead of one path.

Medium

Beautiful Arrangement

The permutations template with a prune baked into the choose step: only place a number at position `i` if it divides `i` evenly or `i` divides it evenly, instead of checking after the fact.

Medium

Restore IP Addresses

Start-index template with exactly 4 segments as the base case; prune any segment that's empty, longer than 3 digits, over 255, or has a leading zero (e.g. "01").

Medium