Introduction to Backtracking Pattern

Introduction to Backtracking Pattern

Backtracking solves a problem by extending a partial solution one choice at a time and immediately checking, after each choice, whether the partial solution can still lead somewhere valid — if it can't (a constraint is violated or a bound is exceeded), the algorithm discards that last choice and tries the next option, instead of exhaustively completing every branch. It is exhaustive search organized as a decision tree, pruned as early as possible.

Recognize the pattern

• The problem asks for all valid arrangements/subsets/paths, or whether any valid one exists (permutations, combinations, subsets, N-Queens, Sudoku, word search, partitioning).
• A solution is built incrementally as a sequence of discrete choices (place item at position i, include/exclude element i, move to next cell).
• There is a constraint that can invalidate a partial solution before it is complete, so you can prune before finishing the branch.
• The state space forms a tree of choices where 'undo the last choice and try another' is meaningful — recursion + explicit undo (state restoration) is the natural implementation.

Brute force vs. optimal (pruned) backtracking

Brute force: generate every complete arrangement, then filter by the constraint at the end. For 3 trees that means all 3! = 6 orderings, each checked once fully built. Cost: build all N! sequences, O(N) each to construct and check → O(N!·N) work regardless of how early a sequence became invalid.

Backtracking: check the constraint after each partial placement. If Apple is placed first and Orange is tried second, the adjacency violation is caught immediately — the whole subtree of completions starting 'Apple, Orange, …' is skipped without ever being generated. Same search space in principle, but dead branches are cut at their root instead of walked to the leaf.

Complexity from first principles

Two different brute-force baselines apply depending on how choices consume the option pool — mixing them up is a common source of wrong complexity claims.

• Independent-choice problems (each of N items independently included or excluded, e.g. subsets): branching factor is a constant b at every level (b = 2 for subsets), so the full decision tree has b^N leaves, and a leaf-only checker costs O(b^N · N) — b^N leaves, each needing O(N) to assemble/verify.
• Consuming-choice problems (each choice removes an option from a shared pool, e.g. ordering N distinct trees, or assigning N non-repeating queen columns): branching factor shrinks every level — N, N−1, N−2, …, 1 — so the brute-force count of complete arrangements is N!, not a fixed-base exponential. Both the tree-planting example and 8-Queens' column assignment are consuming-choice problems: 3! = 6 orderings for the example, 8! = 40,320 column permutations for 8-Queens.

Backtracking with a constraint check at every node visits only the nodes of the search tree that survive pruning, in either model — it never walks a full N! or b^N set of complete leaves. Worst case (constraint never fires until near the end) it still degrades toward that model's brute-force bound; pruning changes the practical/average case, not the theoretical worst case, unless the problem's structure forces early cuts.

For the 3-tree example: the tree that only enforces 'no repeats' (the used[] array, no adjacency check) has 3 + 3·2 + 3·2·1 = 15 nodes (3 at depth 1, 6 at depth 2, 6 at depth 3). Adding the adjacency check prunes the A-O and O-A branches one level early, so only 13 nodes are actually visited — a verified saving of 2 nodes out of 15, counted node-by-node in the trace below (not a claim about leaf count alone). For 8-Queens, the same consuming-choice accounting gives 8! = 40,320 as the brute-force baseline; pruned backtracking with row/column/diagonal checks visits dramatically fewer nodes in practice, but the exact count depends on variable/value ordering and implementation — treat any single figure as an illustrative order-of-magnitude, not a portable constant.

Space is O(N) for the recursion depth and O(N) for the partial-solution buffer that is mutated in place and undone — not O(N) copies, which is why 'undo' (removing the last choice before returning) is essential, not optional.

Traced worked example (every node counted)

Trees: Apple (A), Orange (O), Mango (M). Constraint: A and O cannot be adjacent. Each row below is one candidate the backtracking loop examines — 13 in total. Note the counting convention: rows 2 and 6 (A-O, O-A) are candidates rejected by the constraint check inside the parent's loop, so no recursive call is ever made for them; we count them as pruned nodes of the search tree, giving 11 actual recursive calls + 2 rejected candidates = 13.

Final valid arrangements: [Apple, Mango, Orange] and [Orange, Mango, Apple]. Full accounting: 13 nodes visited versus 15 in the no-adjacency-check tree (3 + 6 + 6) — the adjacency check saves exactly 2 nodes here (the depth-3 children that A-O and O-A would otherwise have produced). The saving is modest at N=3 because branching is already small; it compounds combinatorially as N grows, which is why pruning matters far more on N-Queens-scale problems than on this toy example.

Code: subtree that mirrors the example (generic subset/permutation-style backtracking)

import java.util.*;

class TreeArrangement {
    // Generates all orderings of `trees` where 'A' and 'O' are never adjacent.
    static List<List<String>> solve(List<String> trees) {
        List<List<String>> results = new ArrayList<>();
        boolean[] used = new boolean[trees.size()];
        backtrack(trees, used, new ArrayList<>(), results);
        return results;
    }

    static void backtrack(List<String> trees, boolean[] used,
                           List<String> partial, List<List<String>> results) {
        if (partial.size() == trees.size()) {
            results.add(new ArrayList<>(partial));   // record a full valid solution
            return;
        }
        for (int i = 0; i < trees.size(); i++) {
            if (used[i]) continue;
            String candidate = trees.get(i);
            if (!partial.isEmpty()) {
                String prev = partial.get(partial.size() - 1);
                boolean clashes = (prev.equals("Apple") && candidate.equals("Orange"))
                                || (prev.equals("Orange") && candidate.equals("Apple"));
                if (clashes) continue;               // constraint check -> prune, do not descend
            }
            used[i] = true;
            partial.add(candidate);                  // choose
            backtrack(trees, used, partial, results); // explore
            partial.remove(partial.size() - 1);       // un-choose (the 'backtrack' step)
            used[i] = false;
        }
    }
}

Pitfalls

• Forgetting to undo state (the `remove`/`used[i] = false` lines) — without it, later branches see a corrupted partial solution and either miss valid answers or double-count invalid ones.
• Checking the constraint only at the leaf instead of after each choice — this degrades pruned backtracking back into brute force with extra bookkeeping, losing the whole benefit.
• Mutating and sharing the same list reference when recording a result — must copy (`new ArrayList<>(partial)`), otherwise every stored 'solution' ends up reflecting the final backtracked-to-empty state.
• No visited/used tracking in permutation-style problems — reusing an index leads to invalid repeated elements.
• Conflating brute-force models — quoting a fixed-base b^N bound for a problem whose choices consume a shared pool (permutations, N-Queens columns) overstates or misstates the baseline; that family's brute-force cost is N!, which shrinks branching factor level by level (N, N−1, N−2, …) rather than staying constant.
• Treating backtracking as always exponential in practice — for constraint-heavy problems, pruning can make runtime close to linear in the number of valid solutions; the real cost is proportional to the (much smaller) explored tree, not the full search space.

When to use / when not — trade-offs vs. Dynamic Programming

Use backtracking when you need to enumerate all valid solutions, or find one/any valid solution, and there is a per-step constraint that lets you prune (permutations, combinations, N-Queens, Sudoku, maze/path search with dead ends, subset generation).

Avoid it when the problem asks for an optimal value (min/max cost, count of ways) over overlapping subproblems — that is Dynamic Programming's job. DP also 'tries all possibilities' conceptually, but it memoizes results of repeated subproblems to avoid recomputation and answers optimization questions; backtracking recomputes along fresh paths (no memo table, because each path's validity generally depends on the specific sequence of choices, not just a reusable subproblem key) and answers existence/enumeration questions. If a backtracking solution has overlapping subproblems and only needs an optimal value, converting to DP (or adding memoization on top of the recursion) is usually the right upgrade — otherwise you pay exponential/factorial time for something DP solves in polynomial time.

Takeaways

• Backtracking = build incrementally + check constraint at every step + undo on failure — pruning at the node, not just at the leaf, is what separates it from brute force.
• Worst-case time matches the brute-force baseline for the problem's choice model: O(b^N·N) for independent per-level choices (e.g. subsets), O(N!·N) for consuming/permutation-style choices (e.g. orderings, N-Queens columns) — never mix the two models for the same problem.
• Space is O(N) for recursion depth plus the in-place partial-solution buffer — mutate and undo, don't copy on every call.
• Verify savings claims by counting actual tree nodes (as in the 13-vs-15-node trace above), not by comparing to the count of completed leaves alone — those are different quantities.
• Choose backtracking for 'find all / find any valid' problems; choose DP for 'find the optimal value' problems with overlapping subproblems.

Recall question: In the tree-planting example, why does checking the Apple/Orange adjacency constraint after placing the second tree save exactly 2 nodes compared to the 15-node tree that only avoids repeats?

Adapted and deepened from the course's Backtracking introduction (tree-planting example) with added complexity derivation reconciling independent-choice vs. consuming-choice brute-force models, a fully node-counted trace, a matching diagram, Java implementation, pitfalls, and DP comparison.