Backtracking and Search

Search when alternatives still matter

Define four things before writing the recursion: what the path represents, which choices remain, what completes an answer and what makes completion impossible. For a sum built from candidate indices, the state can include the next allowed index, the running sum and the selected indices.

A small input limit can make exponential search plausible, but it is not a proof of feasibility. Estimate the branching structure and work per output. A sorted list or a fast constraint check can reduce wasted work without changing the worst-case output bound.

Choose, explore, undo

A call owns the changes it makes before descending. The child explores using that changed state. After the child returns, the parent reverses its own changes before trying another child.

# Pseudocode: validity and completion depend on the problem.
def search(state):
    if complete(state):
        emit(copy_answer(state))
        return
    for choice in choices(state):
        if not valid(state, choice):
            continue
        apply(state, choice)
        search(state)
        undo(state, choice)

State restoration is a correctness condition, not cleanup for presentation. If one branch leaves a selected index, board mark or constraint in place, its sibling solves a different problem. Immutable branch arguments avoid some undo operations; shared lists and sets still require ownership.

A copied answer must survive later mutation. Appending the same current list repeatedly stores several references to one changing object. With nested mutable records, a shallow list copy may not be sufficient; copy the answer representation according to its ownership.

The next-choice rule defines the family

For subsets of n distinct indices, the binary decision tree has 2ⁿ leaves. An empty input has one subset: the empty selection. For k-combinations, stop when the selected length reaches k. Reject k outside 0..n under a fixed-size selection contract.

def subsets(values):
    results, path = [], []
    def dfs(i):
        if i == len(values):
            results.append(path.copy())
            return
        path.append(values[i])
        dfs(i + 1)
        path.pop()
        dfs(i + 1)
    dfs(0)
    return results

def combinations(values, k):
    if not 0 <= k <= len(values):
        raise ValueError("k outside 0..n")
    results, path = [], []
    def dfs(start):
        if len(path) == k:
            results.append(path.copy())
            return
        for i in range(start, len(values)):
            path.append(values[i])
            dfs(i + 1)
            path.pop()
    dfs(0)
    return results

A permutation can use a used-index array or swap a chosen element into the next position. Restore the mark or swap after the child returns. The input mutation contract differs even when both methods enumerate the same results.

Palindrome partitioning chooses a valid next substring, then continues from its end. A precomputed validity table avoids rechecking the same substring; interval DP → explains how to fill that table.

Equal values do not imply equal decisions

First decide whether answers distinguish indices or only values. Two equal entries are different index choices, but may produce the same value combination. The algorithm must match that output contract.

# Sorted values; each index usable at most once.
if i > start and values[i] == values[i - 1]:
    continue

This condition skips an equal sibling at one call. It does not ban that value at every depth. With [2,2], selecting the first 2 may still descend and select the second 2. A global “value seen” set would incorrectly remove [2,2].

Permutations need another rule. For sorted values with a used-index array, skip an equal entry when its preceding equal entry has not been used on the current path. This chooses a canonical order for identical copies. A swap-based implementation instead needs depth-local choice deduplication.

Sorting changes caller order if performed in place. Sort a copy when the input must remain unchanged. Preserve original indices separately if they are part of the answer.

Carry the constraints with the branch

Constraint search becomes cheaper when the state stores the reason a choice can fail. Place one queen per row and maintain occupied columns plus diagonal identifiers row+column and row−column. Check membership before placement; add all three identifiers; remove all three on return.

Row uniqueness follows from advancing exactly one row per call. Columns and diagonals need explicit state because future rows can collide with earlier placements. The sets represent the current branch, not every arrangement already explored.

The same design applies to assignment domains, coloring and board digits: store the relevant neighbor or region constraints. Reject invalid choices before expensive descent. More constrained-variable ordering can reduce search, but it does not by itself prove polynomial complexity.

Visited means used on this path

A simple board path must not reuse a cell within one candidate path. Mark a cell after accepting its character or state; explore permitted neighbors; restore the cell or remove its path mark when returning.

A global visited set is different. Graph reachability → can mark a vertex once because future visits do not need a different path history. Board-word search usually does need different histories, so a global mark would discard valid starting paths.

Bounds, movement rules and character mismatch are cheap checks. For many words, walk a trie in parallel and reject a missing prefix before exploring more cells. Trie-guided board search → owns the shared-prefix mechanism. Do not leave the board modified after a successful early return unless mutation is explicitly permitted.

A prune must rule out every completion

For positive candidates, a running sum above the target cannot decrease. With sorted positive candidates, a next candidate that exceeds the remaining target also rules out every later candidate at that call. This justifies stopping the loop, not merely skipping one candidate.

Negative candidates invalidate that argument. A partial sum 5 can still reach target 3 by adding −2. Zero candidates also change termination conditions for reusable choices. State the domain before applying a sum-based prune.

Rejecting an already violated constraint is safe only if later decisions cannot repair it. A partial coloring with an equal-colored fixed neighbor already fails. A temporary imbalance in a problem that allows later repair might not fail.

Use remaining capacity and optimistic bounds

For k-combinations, if path length plus remaining indices is below k, completion is impossible. If every remaining allowed contribution is nonnegative and their total is below the remaining target, the branch cannot reach that target either.

Optimization uses bounds on achievable quality. For maximization, an optimistic upper bound no better than the current best can be pruned when only the optimum value is needed. Enumeration of all tied optima requires a stricter comparison or a different output policy.

The bound must dominate every valid completion, even when it uses a relaxed problem to be cheap. A guess based on average remaining values is not a certified bound. Better choice ordering can find a strong incumbent earlier; it is separate from the correctness of pruning.

Repeated states are not repeated paths

Two branches can have the same remaining problem but different accumulated outputs. Counting or feasibility can often cache a sufficient state. Enumerating complete answers cannot usually replace both branches by one cached boolean: each prefix still contributes its own answers.

A key such as index and remaining sum is sufficient only when all future legality follows from those fields and fixed input. Board paths, occupied columns or other branch constraints may also affect the future. Omitting them merges different problems.

Dynamic Programming → explains sufficient state and merging repeated logical subproblems. Backtracking emphasizes exploring paths with reversible choices; DP emphasizes reusing results for equivalent futures. They can appear together.

Output size is part of the cost

For all subsets, copying selected values costs Θ(n·2ⁿ) total for distinct n-element input, even if tree traversal itself has Θ(2ⁿ) nodes. Permutations require Ω(n·n!) work to materialize all n-element outputs. Streaming can reduce retained output memory but not the work needed to emit those elements.

Report active recursion depth, path/constraint storage and retained output separately. A generator reduces stored answers, but suspended frames still consume state. Branch pruning and ordering improve actual explored work; worst-case bounds must still account for instances where they do not help.

Check restoration, completeness and uniqueness

At a call boundary, write the invariant in one sentence. After a child returns and undo completes, assert that the parent's path, sum and constraint sets equal their pre-choice values.

Test empty input, target zero, impossible completion, duplicate values at different depths, successful early return and repeated calls with the same input. On tiny inputs, compare answers with exhaustive index enumeration after applying the intended value-deduplication policy.

Completeness asks whether every valid answer has a branch. Soundness asks whether every emitted answer is valid. Uniqueness asks whether the same requested answer appears twice. A restoration test alone proves none of these by itself.

Related mechanisms

Choosing Algorithms → distinguishes enumeration from sufficient-state reuse. Tree Traversal → connects recursive execution to visit order.

The trace is an exact small example. It shows no measured speedup and does not predict search size for other constraints.