Lesson 6 · Core algorithms

Backtracking Algorithms

Backtracking is an algorithmic paradigm that incrementally builds candidates to the solutions and abandons a candidate ('backtracks') as soon as it determines that the candidate cannot possibly be completed to a valid solution.

Searching a Tree of Partial Solutions

Backtracking builds a solution incrementally, one decision at a time, and abandons a partial solution the instant it becomes clear it cannot be completed. It is a systematic search — it will find every valid answer — but it avoids examining most of the possibilities by refusing to extend the ones already known to be dead.

The mental model is a state-space tree. The root is the empty solution, each edge is one decision, and each node is the partial solution built by the decisions above it. Leaves at full depth are complete candidates. The algorithm is a depth-first traversal of this tree that never builds the whole thing.

Contrast it with brute force, which generates every complete candidate and tests each at the end. In the eight-queens problem that means checking all 4,426,165,368 board arrangements. Backtracking places one queen per row and rejects a placement the moment it is attacked, cutting the search to roughly 15,000 nodes — the same guarantee of completeness, several orders of magnitude less work.

The distinction from dynamic programming is worth keeping straight, since both are recursive. DP applies when subproblems overlap and results can be reused. Backtracking applies when you are enumerating structurally distinct configurations that share nothing to cache — the work genuinely has to be done, so the saving comes from not doing the impossible parts.

Build incrementally; abandon a branch as soon as it cannot work
The state-space tree is explored depth-first and never materialised
Same completeness as brute force, a fraction of the nodes
Unlike DP, subproblems do not overlap — pruning is the only saving

Choose, Explore, Un-choose

Every backtracking function has the same three-part body, and the third part is the one the technique is named for.

Choose — commit to one option by adding it to the partial solution. Explore — recurse to make the next decision on top of that commitment. Un-choose — remove the option, restoring the state to exactly what it was before this branch was entered.

That final step is what allows a single mutable structure to be reused across the entire search. Without it, state from an abandoned branch leaks into the next one and the results are silently wrong. The invariant to hold in mind is that a function must leave the state exactly as it found it — every mutation on the way down has a matching reversal on the way up.

The undo must mirror the choice precisely. If choosing appended to a list, undoing pops from it; if it set used[i] = true, undoing sets it back to false; if it modified a board cell, undoing restores the previous value. Forgetting one of several mutations is the single most common bug in backtracking code, and it typically produces answers that are correct for the first branch and wrong afterwards.

One alternative avoids the issue: pass a copy of the state into the recursion instead of mutating a shared one. This removes the undo step and is much harder to get wrong, at the cost of O(depth) copying per node. It is a reasonable trade in an interview under time pressure, but the mutate-and-undo form is what production code uses.

When a complete solution is reached, it must be copied into the results list. Appending the working structure itself stores a reference that later mutations will overwrite — producing a result list full of identical or empty entries, a bug that looks baffling until the aliasing is spotted.

Choose, explore, un-choose — the undo restores the state
Every mutation on the way down needs a reversal on the way up
Copying state instead of mutating removes the undo, at a cost
Copy a completed solution into the results, never the live structure

Pruning Is Where the Speed Is

Without pruning, backtracking is brute force with extra steps. Every bit of its advantage comes from cutting branches before they are explored, so the design question for any backtracking problem is: what is the earliest point at which this branch is provably hopeless?

A feasibility check rejects a choice that violates a constraint immediately. In N-Queens, a queen is rejected the moment it shares a column or diagonal with one already placed — the check happens before recursing, not after a full board is built.

A bound check rejects a branch that cannot beat the best answer found so far. If the partial sum already exceeds the target and all remaining values are positive, no completion can work. This is the basis of branch and bound, and it strengthens as better solutions are found.

Ordering the choices amplifies both. Trying the most constrained option first — the cell with the fewest legal values in a Sudoku, the largest item first in a packing problem — causes failures to surface near the root, where a single cut removes an exponentially large subtree. Sorting the input often serves the same purpose for a fraction of the effort.

The economics are worth stating plainly: pruning at depth d in a tree with branching factor b removes roughly b^(depth − d) nodes. A cut near the root is worth exponentially more than a cut near the leaves, which is why the effort belongs in checking early rather than in optimising the leaf test.

Ask what makes a branch hopeless, and test it before recursing
Feasibility rejects invalid states; bounds reject unwinnable ones
Try the most constrained choice first to fail near the root
A cut high in the tree removes exponentially more work

Key reference

Terms, operations, and practical uses

Core vocabulary

State SpaceThe set of all possible configurations or paths for a given problem.
CandidateA partial or complete solution currently being evaluated.
PruningStopping the exploration of a path as soon as it's known it cannot lead to a valid solution.

Mechanics

Recursive DepthThe depth of the recursive call stack, which usually corresponds to the number of choices made so far.
Backtrack (Undo)The crucial step of reverting a choice (e.g., popping from an array) after the recursive call returns.
Base CaseThe condition under which a candidate is complete and can be added to the final results.

Common patterns

SubsetsGenerating all possible subsets (the power set) by deciding whether to include or exclude each element.
PermutationsGenerating all possible orderings of a set, typically requiring a 'visited' array to avoid reusing elements.
CombinationsSelecting K items from N possibilities without regard to order, typically tracked via a start_index.

Implementation

Generate all subsets of [1, 2]

def subsets(nums):
    res = []
    def backtrack(start, path):
        res.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    backtrack(0, [])
    return res
print(subsets([1, 2]))

#include <iostream>
#include <vector>
using namespace std;
void backtrack(int start, vector<int>& path, vector<int>& nums, vector<vector<int>>& res) {
    res.push_back(path);
    for (int i = start; i < nums.size(); i++) {
        path.push_back(nums[i]);
        backtrack(i + 1, path, nums, res);
        path.pop_back();
    }
}
vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> res;
    vector<int> path;
    backtrack(0, path, nums, res);
    return res;
}
int main() {
    vector<int> nums = {1, 2};
    vector<vector<int>> res = subsets(nums);
    cout << '[';
    for (size_t i = 0; i < res.size(); i++) {
        if (i) cout << ", ";
        cout << '[';
        for (size_t j = 0; j < res[i].size(); j++) {
            if (j) cout << ", ";
            cout << res[i][j];
        }
        cout << ']';
    }
    cout << "]\n";
}

import java.util.*;
public class Main {
    static void backtrack(int start, List<Integer> path, int[] nums, List<List<Integer>> res) {
        res.add(new ArrayList<>(path));
        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            backtrack(i + 1, path, nums, res);
            path.remove(path.size() - 1);
        }
    }
    static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(0, new ArrayList<>(), nums, res);
        return res;
    }
    public static void main(String[] args) {
        System.out.println(subsets(new int[]{1, 2}));
    }
}

Watch it run

Step through it

Running on nums = [1, 2]

Output

Read all 7 Steps

Visit the root backtrack(0, []) records the empty path immediately. Every node in this tree is recorded on entry, before any choice is made.
Choose 1 The loop appends nums[0] = 1 and recurses into backtrack(1, [1]). Descending an edge means committing to one choice.
Choose 2 From [1] the loop appends nums[1] = 2 and recurses into backtrack(2, [1,2]). This is the deepest node on this branch.
Undo back to [1] start equals len(nums), so the loop body never runs and the call returns. path.pop() removes the 2, restoring the caller's state to [1].
Undo back to the root The [1] branch is exhausted, so it returns too and path.pop() removes the 1. Undoing each choice on the way out is what makes one shared list safe to reuse.
Choose 2 from the root The root loop advances to i = 1 and appends nums[1] = 2, recursing into backtrack(2, [2]). Because start is 1, the value 1 is never reconsidered, so no subset repeats.
Every subset generated The last branch returns and the root loop ends. Four nodes were visited and four subsets recorded, one per node of the decision tree.

One Template, Three Classic Problems

Subsets. At each index there are two decisions: include this element or skip it. The tree is binary and depth n, so there are 2^n leaves — matching the number of subsets exactly, which is why no pruning is possible when all subsets are wanted. Every node is recorded, not only the leaves, because every partial state is itself a valid subset.

Permutations. At each position, choose any element not yet used. Branching starts at n and shrinks by one each level, giving n! leaves. A boolean used array tracks what is taken; the alternative is swapping elements into position and swapping back, which avoids the extra array.

N-Queens. Place one queen per row and try each column. The constraint check is the entire algorithm: a column is legal if no earlier queen shares it or either diagonal. Tracking three sets — columns, and the two diagonal indices row − col and row + col — makes that check O(1) rather than a scan over placed queens.

Duplicate handling is the detail that separates a working solution from a nearly working one. When the input contains repeated values, sort it first, then within a single level of recursion skip an element identical to the previous one. The rule is precise: skip when i > start && nums[i] == nums[i-1]. Comparing against the previous sibling prevents duplicate branches at the same level while still allowing the value to be reused at deeper levels, which is exactly the behaviour required.

The complexity follows from the tree's shape rather than from analysing the code: multiply the number of nodes by the work done at each. Subsets are O(n · 2^n) — 2^n subsets, O(n) to copy each. Permutations are O(n · n!). N-Queens has no clean closed form, which is precisely why pruning matters there and why the practical runtime is so far below the theoretical bound.

The three standard problems and what changes between them
Problem	Choice at each step	Leaves	Key detail
Subsets	Include or skip element i	2^n	Record every node, not just leaves
Permutations	Any unused element	n!	`used` array, or swap and swap back
Combinations	Any element after index i	C(n,k)	Pass `start` to prevent reuse
N-Queens	A column in this row	≈ pruned	Track column and both diagonals as sets

Subsets branch two ways; permutations branch over what is unused
Pass a start index to stop combinations repeating elements
N-Queens tracks column, row − col, and row + col
Sort, then skip nums[i] == nums[i-1] when i > start, for duplicates