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 copy of yourself to solve a smaller version of the problem. Backtracking is this same trick, plus one new move: try a choice, recurse as if it were correct, and if it is wrong (or you have explored everything reachable from it), undo the choice and try the next one. The undo is the new part. Plain recursion never takes anything back. Backtracking does, on purpose, every time.

Imagine that you explore a maze. At a fork, you commit to a path and keep walking. If it ends in a dead end, you do not restart from the entrance. You walk back to the last fork and try a direction that you have not tried yet. That walk back is the backtrack. You do not give up. You return 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 that 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 reached 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), and un-choose (remove it before the next iteration tries a different option). To skip the un-choose step is the most common bug in this whole 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. There is nothing to un-choose; you added nothing.
        backtrack(i + 1)

    backtrack(0)
    return result

There are two recursive calls per index, one for "in" and one for "out". This is 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 two times in one permutation. The first position has n choices, the second has n-1, the 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:                 // look only forward from 'start'
            current.add(i)                 // choose
            backtrack(i + 1)               // explore: the 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 be generated as if they were different combinations, but a combination does not care about order. If you force every recursive call to pick only indices at or after 'start', each group of elements can be built in only 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: reached the target exactly
            result.add(copy of current)
            return
        if remaining < 0:                  // PRUNE: overshot, no reason to continue
            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 the exploration of a branch the instant it is provably dead, instead of a walk all the way down to a base case that was never going to succeed. Without it, the function still gets the right answer in the end. It just does far more work to get there. Pruning does not 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 is usually no 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)	There are two choices (include or exclude), repeated for each of n elements. So the recursion tree has 2ⁿ leaves. The space is only 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)	There are n choices for the first slot, n-1 for the second, and so on. That product is n!. The 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)	This is bounded by how many size-k groups exist. In the worst case (k around n/2), that is still exponential in n. The stack holds only the current partial combination, which never exceeds size k.
any backtracking search, generally	exponential or factorial	O(depth of recursion)	This is the same call-stack-cost lesson as Recursion Basics. The number of pending calls that wait on the stack at any moment is what space measures. That is 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 most common backtracking bug. If `current.remove(...)` is missing (or runs before the recursive call instead of after), the partial solution keeps garbage from a branch that you have already explored. Later branches then see state left over from earlier branches instead of the clean slate that they should get. The symptom is usually "answers that look almost right, with extra or duplicated elements that do not belong".

Duplicate input values without duplicate-skipping logic

the input has repeated values, for example [1, 1, 2]

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

Missing or wrong base case

the recursion never records a completed answer, or never stops

This is the same failure family as Recursion Basics. No base case (or one that is never reached) means that the function recurses until it overflows the call stack. A base case that is technically present but wrong (for example, a check of `i > len(nums)` instead of `i == len(nums)`) can quietly skip the record of 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 still finds every valid combination. It is not wrong, only slow, because it keeps a recursion down branches where `remaining` already went negative instead of a cut of them immediately. The worst case does not change asymptotically. But in practice the difference between pruning and no pruning is often the difference between an instant finish and a timeout.

Use It

Subsets

Use the choose/explore/un-choose template, exactly. At each index, recurse one time with the element included and one time without it.

Medium

Subsets II

This is the same as Subsets, but the input has duplicates. Sort first. Then skip an index if it equals the previous index and the previous one was not chosen at this level.

Medium

Permutations

Use the used-array template. At every position, try every not-yet-used element, mark it used, recurse, then unmark it.

Medium

Permutations II

This is Permutations with duplicate values. Sort first. At each position, skip a value if it equals the previous value and the previous one is currently unused (which means it was already fully explored and backtracked out).

Medium

Combinations

Use the start-index template, exactly. Recurse forward from `start`. Stop once the partial combination reaches size k.

Medium

Combination Sum

This is Combinations plus a target-sum prune. Pass `i` (not `i + 1`) to the recursive call, because each number can be reused. Prune the instant the remaining target becomes negative.

Medium

Combination Sum II

This is Combination Sum, but each number can be used only one time and the input has duplicates. Pass `i + 1` forward. Sort first. Skip a value equal to the previous one at the same recursion level.

Medium

Letter Combinations of a Phone Number

This is the same shape as permutations of a fixed length. At digit index i, choose one of the letters of that digit, recurse to digit i+1, then un-choose.

Medium

Palindrome Partitioning

Use the start-index template again. At position `start`, try every cut point ahead of it, but recurse only 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 the close-count would exceed the open-count. Accept a complete answer only once both counts equal n.

Medium

Word Search

Choose a direction to step from the current grid cell, explore, then un-choose by removing the visited mark from that cell. 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

Use the permutations template with a prune in the choose step. Place a number at position `i` only if it divides `i` evenly or `i` divides it evenly, instead of a check after the fact.

Medium

Restore IP Addresses

Use the start-index template with exactly 4 segments as the base case. Prune any segment that is empty, longer than 3 digits, over 255, or has a leading zero (for example "01").

Medium