Backtracking

What it is

Backtracking builds a solution one decision at a time. Whenever a partial solution cannot lead to a valid answer, it abandons that branch and returns to the previous decision.

The search forms a tree: each node is a partial solution, and each edge adds a choice. A recursive call explores one subtree. Returning from the call restores the parent state so another choice can be tried.

Compared with generating every complete candidate and checking afterward, backtracking can reject invalid candidates early. It also avoids exploring choices that cannot satisfy the remaining requirements. Worst-case running time is usually still exponential or factorial, but effective pruning can shrink the explored tree substantially.

Backtracking supports three different goals:

• Enumeration: collect every valid solution.
• Decision: stop when any valid solution is found.
• Optimization: find the best solution, using bounds to discard uncompetitive branches.

How to recognize it

Look for these signals:

• The task asks for all subsets, combinations, permutations, partitions, paths, or assignments satisfying constraints.
• A solution is naturally constructed through a sequence of discrete choices.
• Choices affect which later choices are legal: used elements, occupied positions, remaining budget, or running balance.
• Input sizes are small enough to permit exponential search, especially after pruning.
• Requirements include an exact count, exact total, precedence relationships, or compatibility restrictions.
• The task asks for the first valid answer under a specified ordering, or the minimum-cost valid assignment.

Backtracking is not automatically the best choice whenever choices exist. If many search histories produce the same relevant state, dynamic programming may avoid repeated work. If a provably safe local choice exists, a greedy method may eliminate search entirely.

The core technique

Every recursive search needs four ingredients:

1. State: everything needed to determine legal continuations.
2. Choices: decisions available from that state.
3. Termination: how to recognize a complete solution.
4. Pruning: conditions proving that completion is impossible or unnecessary.

The central pattern is choose, recurse, undo. Maintain an invariant: when a recursive call begins, its state describes exactly the current partial solution.

1. Subsets and fixed-size combinations

Use include/exclude decisions to enumerate arbitrary subsets. For fixed-size combinations, choosing the next index from an increasing range is often cleaner. Increasing indices ensure that each selection appears once, rather than once for every ordering.

def combinations(items, k):
    answers, path = [], []
    n = len(items)

    def dfs(start):
        need = k - len(path)
        if need == 0:
            answers.append(path.copy())
            return
        if n - start < need:
            return

        for i in range(start, n - need + 1):
            path.append(items[i])
            dfs(i + 1)
            path.pop()

    if 0 <= k <= n:
        dfs(0)
    return answers

The capacity bound rejects states with too few remaining elements. Additional spacing restrictions can advance the next starting index farther and tighten the maximum selectable count. Such bounds must overestimate, never underestimate, how much can still be selected.

2. Permutations and ordered choices

Use a used array or bitmask when order matters and each input element may appear at most once. Unlike combinations, every unused index remains a candidate at every depth.

def constrained_permutations(items, compatible):
    answers, path = [], []
    used = [False] * len(items)

    def dfs():
        if len(path) == len(items):
            answers.append(path.copy())
            return

        for i, value in enumerate(items):
            if used[i]:
                continue
            if path and not compatible(path[-1], value):
                continue
            used[i] = True
            path.append(value)
            dfs()
            path.pop()
            used[i] = False

    dfs()
    return answers

Compatibility checks reject invalid adjacent choices immediately. More general restrictions can inspect the whole state.

Distinguish index permutations from distinct value permutations. Equal values at different indices are separate choices in the former. For distinct value permutations, sort the input and skip equivalent choices at the same recursion depth.

To find the lexicographically first valid sequence, explore choices in lexicographic order and stop at the first complete answer. This requires the traversal order to match the requested output order.

3. Constrained sequences, paths, and partitions

Use this variant when each choice changes a running quantity or extends a structured object.

For a fixed-length action sequence, track position and running balance. Reject a move immediately if it crosses an allowed bound. Also check whether the remaining steps can reach the required final balance. If each step changes balance by one, both distance and parity matter.

For paths, track the current location, visited locations, and any required counters. Mark a location before recursion and unmark it afterward. Check the next required label and update counters only when the corresponding event occurs.

For contiguous partitions, choose the next boundary and recurse on the remaining suffix. Precompute reusable predicates, such as whether each substring is palindromic. With an exact piece count, reject suffixes that cannot supply enough pieces. A suffix-feasibility table can make this check stronger than a simple length bound.

These searches share the same principle: maintain constraints incrementally instead of rebuilding and checking complete candidates.

4. Assignments, feasibility, and optimization

Use assignment search to distribute elements among groups or place objects into available positions. Track each group's relevant totals, counts, or occupied resources.

Try restrictive choices early. Assigning larger nonnegative values first often exposes capacity violations sooner. Another common heuristic chooses the unassigned variable with the fewest legal options. In exact-cover search, this means branching on the least-flexible uncovered item.

Eliminate symmetric branches when interchangeable groups have identical relevant states. For example, assigning an element to either of two groups with equal sums and counts produces equivalent subproblems. Do not apply this rule when group identities carry different constraints.

For minimum-cost search, maintain an incumbent complete cost. Prune when:

cost_so_far + lower_bound_on_completion >= incumbent

The lower bound must never exceed the true minimum completion cost. Ignoring some constraints can produce a useful relaxation. If ties require a canonical answer, equality pruning is safe only when it cannot discard a preferred equal-cost solution.

Memoize failed states or completion costs when different histories reach the same subproblem. Include every fact that affects future legality; a partial key can incorrectly merge distinct states.

Common mistakes

• Missing undo operations: restore paths, visited flags, counters, and resource masks after recursion, including early returns.
• Saving a mutable path directly: copy it when recording an answer.
• Unsafe pruning: a likely failure is not proof that every continuation fails.
• Wrong numeric assumptions: exceeding a target permits pruning for nonnegative additions, but not when later negative values are allowed.
• Confusing duplicates with symmetry: decide whether answers distinguish indices, values, or group labels before skipping branches.
• Premature termination: reaching a target total is insufficient if required counts or other constraints remain unsatisfied.

Complexity

Complexity depends on the explored search tree and work per node:

• Subset enumeration has up to 2^n candidates.
• Fixed-size combinations have C(n, k) answers; copying them costs at least O(k · C(n, k)).
• Permutations have n! answers; storing them costs O(n · n!).
• Assigning n elements to k groups has up to k^n choice sequences.

Pruning improves practical performance but usually does not change these worst-case growth rates.

Auxiliary space is typically proportional to recursion depth plus mutable state. Stored answers, preprocessing tables, and memoization caches are additional costs and may dominate memory usage.