Skip to content
Data Structures & Algorithms

Backtracking interview questions and answers

35 questions, 24 with code. About 3 h 15 min to read them all.

By TestLab · Updated

Plan for an interview
35 questions

Track what you know and what to revise.

Sign in to track progress

You can open a few full answers without signing in. Sign in to read all

1

What is backtracking in algorithm design?

Backtracking is an algorithm design technique that constructs a solution incrementally, explores each valid choice, and abandons partial solutions that cannot lead to a valid answer. It is especially useful for constraint-based problems such as permutations, combinations, N-Queens, Sudoku, and word search.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea

Backtracking follows a choose / explore / un-choose pattern:

  1. Choose: Add a valid option to the current partial solution.

  2. Explore: Recursively investigate completions that include that option.

  3. Un-choose: Remove the option and restore the previous state before trying the next branch.

The main state usually contains:

  • Current path: The partial solution being constructed.

  • Choice state: Information such as a used set or indexes already selected.

  • Constraints: Conditions that each candidate must satisfy.

  • Base case: The condition that identifies a complete solution, such as every position being filled.

A branch can be pruned when a constraint proves that it cannot produce a valid completion. Pruning is safe because every solution extending that branch would violate the same constraint.

Pruning and Example

For permutations of [1, 2]:

  1. Choose 1, making the current path [1].

  2. Explore that branch by choosing 2, producing the complete permutation [1, 2].

  3. Un-choose 2 and then 1, restoring the empty path.

  4. Choose 2 and explore it by choosing 1, producing [2, 1].

  5. Un-choose 1 and 2 after recording the result.

For duplicate values, equivalent branches can be pruned at the same recursion depth so that equal values are treated as indistinguishable. A typical implementation sorts a copy of the input and uses a used_indices set to select candidates without repeating an index.

Other important edge cases include:

  • Empty input: A permutation generator commonly returns one empty permutation, [[]].

  • One element: It produces one permutation.

  • Duplicates: They may represent indistinguishable values or distinct items, depending on the problem.

  • Negative numbers: They are handled like other sortable values.

  • Already sorted input: It does not change the set of permutations.

  • Cycles and disconnected graphs: Graph searches normally require a visited set to prevent repeated visits.

Complexity

Backtracking complexity depends on the search space and the amount of pruning.

  • Exhaustive permutations of n distinct values: Best, average, and worst-case time are all O(n × n!), because there are n! permutations and copying each result takes O(n).

  • Search size: Permutation enumeration has O(n!) raw recursive states and O(n × n!) overall search-and-result size when each completed permutation contains n values. Subsets commonly have O(n × 2^n) search-and-result size.

  • Constrained problems: Best-case time can be substantially lower when strong pruning finds a solution quickly, while worst-case time remains exponential or factorial.

  • Auxiliary space: Typically O(d + s), where d is the recursion depth and s is the size of per-level tracking state; the recursion stack is included. For permutation generation, this is O(n). The input itself is not counted unless the algorithm mutates it.

  • Result storage: Exhaustive permutation generation requires O(n × n!) space when all results are retained.

These bounds are exponential or worse and are not polynomial in the general case.

Common Pitfalls and Interview Tips

  • Forgetting to un-choose: Always restore the path and choice state after exploring a branch.

  • Incorrect base case: Define exactly when a partial solution is complete.

  • Unsafe pruning: Prune only when the constraint guarantees that no valid completion exists.

  • Storing mutable paths directly: Copy each completed path before appending it to the results.

  • Mutating the input: Preserve it unless modification is part of the contract.

  • Ignoring duplicate handling: Decide whether equal values are distinguishable.

  • Recursion depth: Large inputs may exceed Python’s default recursion limit; use an explicit stack or raise the limit deliberately.

  • Graph traversal mistakes: Use a visited set for cycles and disconnected components.

  • Off-by-one errors: Check depth, index, and completion conditions carefully.

  • Other languages: Account for possible integer overflow when computing sizes or combinatorial values.

Interviewers commonly ask which state must be restored, how pruning improves the worst case, how duplicates are handled, and whether the recursion depth could exceed the language’s limit.

3

How does a decision tree work in backtracking?

A decision tree is the conceptual search tree used to organize the choices explored by a backtracking algorithm. Each node represents a partial solution, each branch represents a possible next choice, and each leaf represents a complete solution or a state rejected by a constraint.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The root represents the empty partial solution. At each node, the algorithm:

  1. Selects one available choice.

  2. Extends the partial solution with that choice.

  3. Recursively explores the resulting subtree.

  4. Removes the choice and restores the previous state.

  5. Tries the next available branch.

Backtracking usually traverses this tree depth-first. It does not need to store the entire tree; it stores only the state required to continue along the current path and restore it when returning.

State and the Choose/Explore/Un-Choose Template

A typical recursive state contains:

  • Current path: The choices selected so far.

  • Used set or used indices: The choices unavailable on the current path.

  • Start index or recursion depth: The next decision-tree level being explored.

  • Base case: The condition indicating that the current path is a complete solution.

The three phases are:

  • Choose: Add one valid option to the current path and update the relevant state.

  • Explore: Recursively process the remaining decisions.

  • Un-choose: Reverse the state changes so another branch can be explored safely.

The state must be restored exactly as it was before the recursive call. A complete solution should be copied into the results rather than storing a reference to the mutable path.

Pruning

Pruning cuts off a branch as soon as it cannot produce a valid result. Common checks include:

  • Skip a candidate index already present in used_indices.

  • Reject a partial assignment that already violates a constraint.

  • Stop when too few eligible choices remain to complete the path.

  • Detect repeated states or forbidden cycles in state-space searches.

Constraint-based pruning is safe because adding further choices cannot repair a state that already violates a required condition. Resource-based pruning is safe when its remaining-choice calculation accurately accounts for all future requirements.

Small Walkthrough

For the values [1, 2], consider generating permutations:

  1. At the root, choose 1; the current path becomes [1].

  2. Choose 2; the path becomes [1, 2], so the base case records it.

  3. Un-choose 2, restoring [1].

  4. Un-choose 1, restoring the empty path.

  5. Choose 2, then choose 1; the base case records [2, 1].

The tree has one root, two nodes at the next level, and two leaves.

Complexity

For the illustrative unpruned permutation search:

Case Time Reason
Best O(n × n!) All n! permutations must be generated and copied.
Average O(n × n!) Exhaustive enumeration visits every valid branch.
Worst O(n × n!) The search still has n! leaves and O(n!) internal states.

The search space contains n! leaves, so it is factorial and super-exponential rather than polynomial.

  • Auxiliary space: O(n), including the current path, used set, and recursion stack.

  • Input space: The input list is not counted.

  • Output space: Θ(n × n!) when every permutation is copied into a result list.

If results are generated without being retained, the output-space term is omitted, while the O(n) auxiliary space remains.

Common Pitfalls

  • Incorrect restoration: Failing to undo a choice corrupts the state for later branches.

  • Mutable result references: Copy the current path when recording a solution.

  • Duplicate handling: State whether equal values are distinct positions or whether duplicate results should be suppressed.

  • Edge cases: Empty input returns the empty permutation, one element returns one permutation, and negative or already sorted values require no special handling in this example.

  • Recursion depth: The recursion depth is O(n). Large inputs may require an explicit stack or a carefully increased recursion limit.

  • Graph variants: Disconnected graphs require an outer traversal, while cycles require explicit path or visited-state handling.

  • Common follow-up: Interviewers often ask how constraint checking improves pruning, how the tree size changes, or how the same model applies to N-Queens, Sudoku, and word search.

4

What are common backtracking optimizations

Backtracking optimizations reduce the number of states explored by pruning invalid branches, eliminating duplicate work, caching equivalent states, and using better ordering heuristics. Every optimization must preserve all required solutions; a shortcut that removes a valid solution is incorrect.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Optimization Works

Use the standard choose / explore / un-choose sequence:

  1. Choose: add one candidate to the current state.

  2. Explore: recursively search the branch created by that choice.

  3. Un-choose: restore the state before trying the next candidate.

The state should contain everything needed to determine valid continuations, such as the current path, start index, remaining target, used values, or a path-specific visited set. The base case must be explicit: for example, record the current path when the remaining target becomes zero, or return when no candidates remain.

Common Optimizations

  • Constraint-based pruning: Stop a branch as soon as a necessary condition fails. For example, with sorted positive candidates and a target sum, break when the current candidate would exceed the target. This reasoning is unsafe when negative candidates are allowed.

  • Duplicate elimination: Sort candidates and skip equal values at the same recursion depth. This avoids repeated solutions caused by duplicate input elements, but it also removes solutions that differ only in which equal-valued occurrence was selected.

  • Symmetry breaking: Prune branches that are equivalent under a known symmetry. For example, in an unordered selection problem, require the first selected element to have the smallest possible index.

  • Ordering heuristics: Try candidates likely to produce a solution first. Ordering improves early discovery, but it reduces work only when it enables a proven safe early termination.

  • Memoization: Cache results for equivalent states when different paths can reach the same subproblem. The cache key must capture every condition that affects future choices.

  • Constraint propagation: Update the remaining choices immediately after a selection instead of waiting for later recursion levels to rediscover the conflict.

  • Incremental state checks: Maintain constraints such as the current sum, remaining capacity, or forbidden values as choices are made rather than recomputing them from the entire path.

  • Visited-state handling: Use a path-local set to prevent cycles while allowing a node to appear in different branches. Use a global visited set only when revisiting that node can never produce a distinct valid result.

Complexity

The search space is exponential in general. The cost of copying or materializing solutions can add another factor.

Problem Search-space size Typical time
Subsets 2^n candidate subsets O(n * 2^n)
Permutations n! candidates O(n * n!)
General search Up to b^d nodes for branching factor b and depth d O(b^d) node visits, plus per-node work

For exhaustive subset and permutation enumeration, best, average, and worst-case time are the same asymptotically because every result must be generated. Pruning can reduce actual work for particular inputs, but it does not improve the general worst-case bound. With memoization, time is O(S * T), where S is the number of distinct states and T is the transition cost per state; this may still be exponential.

Auxiliary space includes the recursion stack, current path, and state-tracking structures: typically O(d + m), where d is recursion depth and m is the number of tracked states. The input is not counted. Output space is separate, such as O(n * 2^n) when every subset is copied.

Small Walkthrough

For positive sorted candidates [2, 2, 3] and target 4:

  1. Choose the first 2; the current path is [2] and the remaining target is 2.

  2. Explore choosing the next 2; the path [2, 2] reaches the target, so append a copy.

  3. Un-choose that 2. Trying 3 would exceed the target, so that branch is pruned.

  4. Un-choose the root 2. The second 2 is skipped because an equal candidate was already tried at this depth.

  5. Choose 3; no remaining candidate fits the remaining target 1, so the branch ends.

The only result is [2, 2].

Common Pitfalls

  • Pruning without proving that excluded branches cannot contain valid solutions.

  • Applying sum-based pruning to negative values.

  • Assuming sorted input removes duplicates automatically.

  • Failing to restore mutable state during the un-choose step.

  • Appending the path itself instead of a copy.

  • Using the wrong visited scope and either allowing cycles or discarding valid paths.

  • Ignoring empty-input semantics, one-element inputs, already sorted inputs, disconnected graph components, and cycles.

  • Exceeding Python’s default recursion limit; use an explicit stack when the search depth may approach or exceed 1,000.

5

How do backtracking and divide-and-conquer algorithms differ?

Backtracking and divide and conquer are both recursive techniques, but they solve different kinds of problems. Backtracking explores possible choices and undoes decisions when they fail, while divide and conquer decomposes a problem into smaller subproblems and combines their results.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Relationship

Both approaches commonly use a recursive function with:

  • A base case that records or returns a completed result.

  • A smaller subproblem or unexplored state on each recursive call.

  • Restrictions that prevent invalid or unnecessary exploration.

The key difference is what happens after a recursive call:

  • Backtracking restores the previous state before trying another choice.

  • Divide and conquer usually processes independent subproblems and combines their answers.

Memoized backtracking can overlap with dynamic programming: if two paths reach the same state, cache that state’s result instead of recomputing it.

Key Differences

Aspect Backtracking Divide and Conquer
Main goal Find valid choices or solutions Solve a decomposable problem efficiently
Recursive state Often a mutable partial solution Usually an independent subproblem
State restoration Must undo each choice with an “un-choose” step Usually not needed
Overlapping work Common unless memoization is added Subproblems are usually non-overlapping
Combining results Often records complete solutions directly Usually combines subproblem results
Typical complexity Frequently exponential or factorial Often polynomial or logarithmic
Common examples N-Queens, Sudoku, subset generation Merge sort, binary search, FFT

A practical distinction is that divide and conquer is usually preferable when a problem has a proven recursive decomposition. Backtracking is appropriate when valid solutions can be constructed incrementally but invalid branches can be detected and pruned.

Complexity

For backtracking, complexity depends on the number of states explored and the work performed per state:

  • Subset generation: searches O(2^n) states; copying every result makes total time O(n * 2^n).

  • Permutation generation: searches up to O(n!) permutations; copying results gives O(n * n!) time.

  • Sudoku: may explore up to O(9^m) cell assignments for m empty cells.

These are exponential or factorial search spaces. Pruning can reduce practical runtime, but it does not change the underlying worst-case bound.

For comparison, merge sort takes O(n log n) time in all cases and O(n) auxiliary space. Quicksort takes O(n log n) on average and O(n²) in the worst case, with average stack space O(log n) and worst-case stack space O(n).

Common Pitfalls

  • Forgetting to un-choose: Leaving stale values in the current path causes later branches to contain invalid state.

  • Incorrect pruning: A branch may be pruned only when it provably cannot produce a valid result.

  • Ignoring output cost: Counting only recursive states can understate runtime when every solution is copied.

  • Duplicate handling: If the problem requires unique combinations/permutations, duplicate values must be handled explicitly (e.g., by sorting and skipping).

  • Input mutation: Avoid modifying the caller’s data unless intended.

  • Graph assumptions: For graph problems, disconnected graphs require separate starting points, while cycles require a visited set.

  • Integer overflow: Python integers do not overflow, but factorial-sized counters in other languages may require capping.

  • Common follow-up: Interviewers often ask which branches can be pruned, why pruning is safe, and whether memoization could eliminate repeated states.

6

How does a state space tree explain backtracking algorithms?

A state space tree represents the potential states reachable through a sequence of choices in a backtracking algorithm. Each node is a partial state, each edge is a decision, and a depth-first traversal models the choose–explore–un-choose cycle; pruned branches belong to the conceptual tree but are not explored.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Role of the State Space Tree

A state space tree separates the search problem into three levels:

  • Root: The initial state before any decision is made.

  • Internal nodes: Partial solutions containing some decisions already made.

  • Leaves: Completed candidates, which constraints may accept or reject.

For example, when generating subsets, the root represents the empty subset. Each node branches by excluding or including the next element. A solution can be identified at a leaf or checked whenever a complete candidate is produced.

The state space tree is usually conceptual rather than explicitly constructed. The recursion stack implicitly represents the path from the root to the current node.

Backtracking and Pruning

Backtracking usually performs a depth-first search of this tree:

  1. Choose: Make one decision and update the current state.

  2. Explore: Recursively investigate the resulting branch.

  3. Un-choose: Restore the previous state so another branch can be attempted.

Pruning cuts off a branch when it is known that the branch cannot produce a valid solution. This is safe only when the pruning condition is proven—for example, when a partial placement violates a constraint or when no completion can satisfy the remaining requirements.

The subset example below performs no pruning because every branch can produce a valid subset. Cutting any branch would remove legitimate results. Duplicate-valued subsets are still generated because elements are distinguished by position.

Complexity

For generating all subsets of n elements:

Measure Best Average Worst Reason
Search-tree nodes O(2^n) O(2^n) O(2^n) Each element has exclude/include choices
Total time O(n · 2^n) O(n · 2^n) O(n · 2^n) Copying each subset takes up to O(n)
Auxiliary space O(n) O(n) O(n) Current path plus recursion stack
Space including output O(n · 2^n) O(n · 2^n) O(n · 2^n) All 2^n subsets are retained

These bounds are exponential because the search space itself is exponential. Input storage occupies O(n) space and is excluded from auxiliary space. Including input storage does not change the O(n · 2^n) total when output is retained.

Code Example

def generate_subsets(values: list[int]) -> list[list[int]]:
    """Return every subset of values, including the empty subset."""
    results: list[list[int]] = []
    current_path: list[int] = []

    def backtrack(start_index: int) -> None:
        # Base case: all elements have been considered.
        if start_index == len(values):
            results.append(current_path.copy())
            return

        # Explore the branch that excludes the current element.
        backtrack(start_index + 1)

        # Choose the current element.
        current_path.append(values[start_index])

        # Explore the branch that includes the current element.
        backtrack(start_index + 1)

        # Un-choose the current element.
        current_path.pop()

    backtrack(0)
    return results


print(generate_subsets([1, 2, 3]))
# [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

The trace begins with the empty subset, explores the branch excluding 1, and records [3], [2], and [2, 3]. It then un-chooses and explores branches containing 1, producing [1], [1, 3], [1, 2], and [1, 2, 3].

Common Pitfalls

  • Confusing the state space tree with the recursion tree: The state space tree represents all potential states; the recursion tree represents only states actually explored.

  • Losing the correct state: A node must contain enough information to determine its children and whether it is valid.

  • Failing to restore state: Forgetting the un-choose step causes later branches to inherit incorrect choices.

  • Storing mutable paths directly: Append current_path.copy() rather than current_path, or every result may change later.

  • Ignoring edge cases: Empty input returns [[]]; one element returns [[], [element]]. Negative values and sorted input do not affect this algorithm, while duplicate values are treated as separate positions.

  • Reaching the recursion limit: This recursive implementation uses O(n) stack frames and can exceed Python 3.12’s default limit of about 1,000 for sufficiently large inputs; use a raised recursion limit or an explicit stack in that case.

  • Incorrect pruning: A branch should only be pruned when no valid completion can exist. Graph-specific cases such as disconnected graphs and cycles do not apply to subset generation.

7

What is constraint satisfaction in backtracking?

Constraint satisfaction in backtracking is the process of finding an assignment of values to variables that satisfies every specified constraint. A solver extends a partial assignment, explores possible choices, and removes choices that cannot lead to a valid completion.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Model

A constraint satisfaction problem usually has three components:

  • Variables: The decisions to be made, such as which color each graph node receives.

  • Domains: The possible values for each variable.

  • Constraints: Conditions that the assignment must satisfy, such as requiring two variables to have different values.

A typical solver returns one satisfying assignment or reports that no solution exists. Finding every solution requires continuing the search after each success, while optimization problems generally require additional techniques such as branch-and-bound.

Choose, Explore, Un-Choice

The search follows a three-step template:

  1. Choose: Select an unassigned variable and a candidate value. The Minimum Remaining Values (MRV) heuristic selects the variable with the fewest currently consistent values.

  2. Explore: Add the value to the current partial assignment, mark the variable as used, and recursively search for a completion.

  3. Un-choose: If exploration fails, remove the value and used-variable mark before trying the next candidate.

The state consists of the current partial assignment, the set of assigned variables, and the remaining candidate information. MRV has no fixed start index because it dynamically chooses the next variable; with a fixed variable order, the start index would be the first unassigned position.

The base case occurs when every variable has been assigned. The solver then returns a copy of the completed assignment. A recursive implementation uses one stack frame per assigned variable, so very large problems may require an explicit stack or a raised recursion limit in Python.

Pruning and Safety

Pruning removes impossible branches early:

  • A candidate is rejected when it makes an already-determined constraint false.

  • After assigning a variable, forward checking can remove incompatible values from neighboring variables’ domains.

  • If a variable has no remaining consistent value, the entire branch is impossible and is abandoned.

This pruning is safe because assigned values do not change within a branch, and removing values that already violate a constraint cannot eliminate a valid completion. MRV changes only the search order; it does not change the set of solutions.

Small Example

Consider variables A and B, with domains A = {red, green} and B = {red, blue}. A constraint requires A and B to differ.

  1. MRV selects A; both red and green remain possible.

  2. The solver chooses A = red.

  3. For B, red is removed because it would violate the constraint, leaving only blue.

  4. The solver assigns B = blue.

  5. Every variable is assigned and the constraint holds, so {A: red, B: blue} is returned.

If no complete assignment had been possible, the solver would un-choose red, try green, and eventually return no solution.

Complexity

Let n be the number of variables, d the maximum domain size, and m the number of constraints.

  • Best case: O(n) assignment steps when the first branch succeeds, before per-node MRV and constraint-evaluation overhead.

  • Average case: There is no universal average bound because performance depends on domain sizes, constraint density, and variable-ordering quality.

  • Worst case: The search tree can contain O(d^n) nodes, which is exponential. Constraint checking and MRV add polynomial overhead but do not remove the exponential worst case.

  • Auxiliary space: O(n) for the current assignment, assigned-variable set, and recursion stack, excluding the input. Including input domains and constraints gives O(nd + m) total storage. An implementation that retains candidate lists in every recursive frame can require up to O(n²d) auxiliary space.

Approach Time Auxiliary space When to use
Exhaustive enumeration O(d^n) assignments O(n) when streamed Constraints are weak or the search space is small
Constraint-guided backtracking O(d^n) worst case, usually fewer explored nodes O(n) basic; potentially O(n²d) with cached candidates Constraints can prune invalid partial assignments early

Common Pitfalls

  • Failing to restore state: Always un-choose the value and assigned-variable mark after a failed branch.

  • Checking constraints too late: Validate fully determined constraints as soon as possible rather than waiting for the final assignment.

  • Mutating caller data: Do not modify the supplied domains or constraints; copy the returned assignment.

  • Ignoring edge cases: An empty problem has the empty assignment, one-variable problems work without constraints, duplicate domain values can be removed, and negative values are ordinary values.

  • Graph assumptions: Disconnected components can be solved independently, while cycles in constraints do not cause repeated assignment because each variable is assigned only once.

  • Numeric concerns: Python integers do not overflow, but fixed-width integers in other languages may require range checks.

  • Forgetting the used set: Without tracking assigned variables, the solver may revisit or reassign variables.

  • Common follow-up: Interviewers may ask how MRV improves pruning, how to support constraints over more than two variables, why the problem remains exponential, or how to enumerate all solutions.

8

How can backtracking be implemented without recursion in Python?

Backtracking can be implemented without recursion by replacing the call stack with an explicit stack of search states. Each frame records the next candidate to explore, while the current path and used set track the choices already made.

Read full answer

Applies toPython 3.12

How It Works

The recursive pattern is:

  1. Choose a candidate.

  2. Explore the resulting state.

  3. Un-choose the candidate when that state is complete or exhausted.

An iterative implementation stores one explicit frame for each active exploration level. When a frame has no remaining candidates, it is popped and its parent’s choice is undone.

For generating permutations, the state consists of:

  • current_path: the elements selected so far.

  • used: the indices already selected, preventing an element from being reused.

  • start_index: the next candidate index to examine in the current frame.

  • Base case: when len(current_path) == len(candidates), a permutation has been completed.

The explicit stack replaces recursion, so the algorithm is not constrained by Python’s recursion-depth limit.

Pruning

A candidate is skipped immediately if its index is already in used. This is safe for permutations because each candidate position may appear at most once in a result.

Other problems may reject candidates that violate a constraint. For example, N-Queens can reject an attacked square, while combination-sum search can prune when the sum exceeds the target only if all remaining candidates are non-negative.

Complexity

For n distinct candidates, there are n! complete permutations. Each result is copied in O(n) time, producing O(n * n!) work and result storage. The factorial search space is exponential in n log n, rather than polynomial.

Python set membership is O(1) on average and O(n) in the generic worst case:

Case Time Reason
Best O(n * n!) No pathological set collisions
Average O(n * n!) Constant-average set operations
Worst O(n * n!) A generic hash-table worst-case bound is usually not assumed for these contiguous integer indices

The auxiliary space is O(n), including the current path, used set, and explicit stack. The O(n) input is not counted as auxiliary space. Retaining every permutation requires O(n * n!) result storage.

Code Example

from collections.abc import Sequence


def iterative_permutations(values: Sequence[int]) -> list[list[int]]:
    """Generate permutations with an explicit stack instead of recursion."""
    candidates = list(values)

    if not candidates:
        return [[]]

    results: list[list[int]] = []
    current_path: list[int] = []
    used: set[int] = set()
    chosen_indices: list[int] = []  # index of each value in current_path

    # Each frame stores the next candidate index to examine.
    stack: list[list[int]] = [[0]]

    while stack:
        frame = stack[-1]
        start_index = frame[0]

        # This frame is exhausted: backtrack to its parent.
        if start_index >= len(candidates):
            stack.pop()
            if current_path:
                current_path.pop()
                used.remove(chosen_indices.pop())
            continue

        frame[0] += 1

        # Prune candidates that were already selected.
        if start_index in used:
            continue

        # Choose
        current_path.append(candidates[start_index])
        chosen_indices.append(start_index)
        used.add(start_index)

        # Explore
        if len(current_path) == len(candidates):
            # Base case: save a copy of the completed path.
            results.append(current_path[:])

            # Un-choose
            current_path.pop()
            used.remove(chosen_indices.pop())
        else:
            # Explore the next level with a new frame.
            stack.append([0])

    return results


print(iterative_permutations([1, 2, 3]))
# Expected output:
# [[1, 2, 3], [1, 3, 2], [2, 1, 3],
#  [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Walkthrough

For [1, 2, 3]:

  1. The root frame chooses 1, producing current_path = [1].

  2. Its child frame chooses 2, producing [1, 2].

  3. The next frame chooses 3, reaching the base case and saving [1, 2, 3].

  4. The algorithm removes 3, tries the remaining alternatives, and eventually produces [2, 1, 3].

  5. Each frame is popped only after its candidates are exhausted, restoring the previous path.

Common Pitfalls

  • Forgetting to un-choose: Remove the selected element when its branch is exhausted.

  • Sharing mutable path objects: Store current_path[:] in results; never append current_path directly.

  • Incorrect frame state: Each child frame must use the correct candidate range. For combinations, its starting index can be the previous choice plus one.

  • Duplicate values: The code treats equal values at different positions as distinct, so duplicate permutations may be produced. Deduplicate results afterward if required.

  • Edge cases: Empty input returns [[]], one element returns [[element]], negative values work normally, and sorted input needs no special handling.

  • Graph variants: Use a separate visited set to prevent cycles and, when required by the problem, traverse disconnected components.

9

How to choose candidates in backtracking

In backtracking, candidate selection means choosing which possible next choices to explore, while pruning discards choices that cannot lead to a valid solution. A correct implementation makes the state, base case, and choose/explore/un-choose steps explicit.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Backtracking maintains the state needed to test the next candidate:

  • Current path: choices selected so far.

  • Used indices: candidates already selected, preventing reuse.

  • Start index: the earliest candidate the next call may choose, preserving canonical order.

  • Base case: stop when the required number of choices has been selected.

  • Choose: add a valid candidate.

  • Explore: recursively try the remaining choices.

  • Un-choose: restore the state before testing the next candidate.

Choosing and Pruning Candidates

  • Hard constraints: Reject candidates violating required conditions immediately.

  • Candidate ordering: Try promising values first, such as values near the target in subset-sum problems. This is a heuristic and can affect when a solution is found, but not which solutions are found.

  • Duplicate avoidance: Sort candidates before skipping equal values at the same recursion level. Equal values may still represent separate occurrences at different levels.

  • Most-constrained variable: In constraint-satisfaction problems, first choose the variable with the fewest legal values, then try those values.

  • Lookahead: Prune only when the constraint is monotonic, meaning an invalid prefix can never become valid after adding more candidates.

  • Bound checking: In optimization problems, discard paths that cannot improve the best result found so far.

Search Space

Problem Worst-case time Auxiliary space, excluding input/output
Subsets O(n · 2ⁿ) O(n)
Permutations O(n · n!) O(n)
Combinations O(k · C(n, k)) O(k)
N-Queens O(n · n!) loose upper bound O(n)
Sudoku with m empty cells O(9ᵐ) with constant-time local checks O(m)

These are exponential-class combinatorial searches; permutation and N-Queens bounds grow more precisely factorially. Pruning reduces the effective branching factor.

Code Example

from collections.abc import Callable


def choose_candidates(
    candidates: list[int],
    count: int,
    is_allowed: Callable[[int], bool] | None = None,
) -> list[list[int]]:
    """Return unique combinations of count candidate values."""
    if count < 0:
        raise ValueError("count must be non-negative")
    if count == 0:
        return [[]]
    if count > len(candidates):
        return []

    ordered = sorted(candidates)
    current_path: list[int] = []
    used_indices: set[int] = set()
    results: list[list[int]] = []

    def search(start_index: int) -> None:
        # Base case: the required path is complete.
        if len(current_path) == count:
            results.append(current_path[:])
            return

        slots_left = count - len(current_path)

        for index in range(start_index, len(ordered) - slots_left + 1):
            candidate = ordered[index]

            # Prune duplicates at this recursion level.
            if index > start_index and candidate == ordered[index - 1]:
                continue
            if index in used_indices:
                continue
            if is_allowed is not None and not is_allowed(candidate):
                continue

            # Choose.
            current_path.append(candidate)
            used_indices.add(index)

            # Explore.
            search(index + 1)

            # Un-choose.
            used_indices.remove(index)
            current_path.pop()

    search(0)
    return results


print(choose_candidates([3, 1, 2, 3], 2))
# [[1, 2], [1, 3], [2, 3], [3, 3]]

Trace for [3, 1, 2, 3]:

  1. Start with current_path = [] and start_index = 0.

  2. Choose 1; the path becomes [1].

  3. Choose 2, producing [1, 2]; copy it into the results and un-choose 2.

  4. Choose 3, producing [1, 3], then backtrack.

  5. After un-choosing 1, choose 2 and then 3, producing [2, 3].

  6. Finally choose the first 3 and then the second 3, producing [3, 3]; the two 3s are separate occurrences, while the duplicate check stops a second [3, ...] branch at the same level.

Complexity and Edge Cases

For n input candidates and k requested choices:

  • Best case: O(n log n) when is_allowed rejects candidates immediately; O(1) when count is zero.

  • Average case: constraint-dependent, ranging from O(n log n) to the exhaustive bound.

  • Worst case: O(n log n + k · C(n, k)).

  • Auxiliary space: O(n + k), including the sorted copy, used set, current path, and recursion stack; input is excluded. Storing R results adds O(kR).

Edge cases include empty input, one element, zero or excessive count, duplicate values, negative values, and already sorted input. The function does not mutate the input. For graph backtracking, use a visited set to reject cycles and start searches in every disconnected component.

Common Pitfalls

  • Off-by-one errors: Check both the base case and the range that leaves enough remaining candidates.

  • Mutating input: Sort a copy or explicitly state that mutation is intended.

  • Forgetting to un-choose: Restore every changed piece of state after recursion.

  • Sharing mutable results: Append current_path[:], not current_path itself.

  • Ignoring cycles: In graph searches, maintain and restore the visited state correctly.

  • Integer overflow: Fixed-width languages may overflow when calculating counts, sums, or factorial-sized bounds.

  • Deep recursion: Python’s default limit is about 1000; use an explicit stack or cautiously raise the limit after checking stack safety.

  • Follow-up: Interviewers commonly ask why a pruning rule is safe, how duplicates are handled, and when DP or meet-in-the-middle would be preferable.

10

How does pruning improve backtracking algorithms?

Pruning eliminates partial states that cannot lead to a valid completed solution, allowing backtracking to reject impossible branches early while preserving every valid solution. It often reduces practical runtime substantially, although it does not generally eliminate an algorithm’s exponential worst case.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Pruning Works

Backtracking uses a choose / explore / un-choose structure:

  • Choose: Add one candidate to the current path.

  • Explore: Recursively investigate the remaining choices.

  • Un-choose: Remove the candidate and restore the previous state.

A branch can be pruned when:

  • A constraint is violated: The current selection already breaks a required rule.

  • Completion is impossible: The remaining choices cannot satisfy the target or constraints.

  • Choices are symmetric: Equivalent branches would generate duplicate results and can be skipped when their equivalence is provable.

  • A limit is reached: Further choices cannot produce an acceptable result.

A pruning condition is safe only if the discarded branch cannot contain any valid completion. Incorrect pruning can remove valid answers.

State and Base Case

For a combination-sum example in which each candidate may be used at most once, the recursive state contains:

  • current_path: the candidates currently selected.

  • remaining: the sum still required.

  • start_index: the first candidate available for the next choice.

Because each recursive call advances start_index, a candidate cannot be selected more than once. The base case is remaining == 0; at that point, a copy of current_path is added to the results.

Example Walkthrough

For candidates [2, 3, 5, 7] and target 10:

Decision Current path Remaining Result
Choose 2 [2] 8 Continue
Choose 3 [2, 3] 5 Continue
Choose 5 [2, 3, 5] 0 Record solution
Un-choose 5, 3, and 2 [] 10 Try another root
Choose 3 [3] 7 Continue
Choose 7 [3, 7] 0 Record solution

After choosing [2, 3], the remaining candidates are 5 and 7. The candidate 7 is pruned because it exceeds the remaining sum of 5; since the candidates are sorted, all later candidates also exceed it.

Complexity

Let n be the number of distinct positive candidates.

  • Search space: O(2^n) possible subsets, which is exponential.

  • Best time: O(n) when the target is zero because reading and validating the input dominates. For a positive target, preparation may require O(n log n) to sort the candidates.

  • Average time: There is no distribution-independent average without specifying a distribution of inputs. Workloads containing exponentially many valid combinations can take O(n2^n) because each stored solution may require O(n) work to copy.

  • Worst time: O(n2^n), including copying exponentially many solutions.

  • Auxiliary space: O(n), excluding the input and returned output but including copied and sorted candidates, the current path, and the recursion stack.

  • Output space: Up to O(n2^n) when exponentially many combinations are valid and stored.

Effective pruning reduces the states actually explored, so it can greatly improve runtime on many instances. It does not, by itself, guarantee a better exponential worst-case bound.

Common Pitfalls

  • Unsound pruning: Never discard a branch merely because it appears unpromising; prove that it cannot contain a valid completion.

  • Incorrect boundary checks: In the positive-candidate example, prune when a candidate is greater than the remaining sum, not when it is equal.

  • Path aliasing: Store a copy of the current path because later backtracking operations mutate it.

  • Duplicate results: Sort and deduplicate candidates when unique value combinations are required.

  • Mutation: Copy and sort candidates rather than modifying the caller’s input.

  • Edge cases: Empty input and a nonmatching single candidate produce no result; duplicate values require an explicit uniqueness policy; negative or zero candidates invalidate the monotonic pruning shown; already sorted input need not be modified. Graph-search variants must additionally account for cycles and disconnected components.

  • Recursion depth: A recursive implementation can require depth proportional to the number of candidates, so very large instances may need an explicit stack or a carefully raised recursion limit.

  • Typical follow-up: Interviewers commonly ask how to prove a pruning condition safe, how duplicates affect completeness, and how the recursive state can be converted to an explicit stack.

11

How does memoization improve backtracking?

Memoization improves backtracking by caching completed subproblems so equivalent states are not solved repeatedly. Backtracking still follows the choose, explore, and un-choose pattern; memoization replaces repeated computation with a lookup.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

In a backtracking algorithm, the search state must completely describe the remaining problem. For combination sum, the relevant memoized state is:

  • start_index: the first candidate that may be selected.

  • remaining: the target value still needed.

  • current_path: the choices already made. It is used during reconstruction but is not part of the cached count because suffix counts do not depend on the selected prefix.

  • Used set: unnecessary because selecting candidates strictly by increasing index prevents repetition.

The recurrence is:

count_suffix(start_index, remaining) = sum of count_suffix(index + 1, remaining - candidate) for every eligible candidate.

The base case returns 1 when remaining == 0, meaning one valid combination has been completed. Memoization stores each (start_index, remaining) result so equivalent suffix problems are calculated only once.

Pruning and Walkthrough

The search prunes a branch when:

  • No candidates remain.

  • The smallest available candidate exceeds remaining.

  • The cached suffix count is zero, meaning no valid completion exists.

For candidates = [2, 3, 4] and target = 7:

Choice Remaining State Result
Select 2 (1, 5) No valid suffix
Select 3 (2, 4) One suffix: [4]
Select 4 (3, 3) No valid suffix

The final result is [[3, 4]].

Complexity

Let n be the number of distinct candidates, S the number of cached states, C the number of returned combinations, and k the maximum combination length.

  • Search space: At most 2^n candidate subsets, so the search space is exponential.

  • Best time: O(n log n) for sorting and deduplication, followed by O(n) search in a simple case.

  • Average time: O(nS + kC), depending on reachable states, successful combinations, and pruning. There is no tighter universal average bound without specifying an input distribution.

  • Worst time: O(n * 2^n) because each memoized state may scan n candidates and reconstructing all combinations can also take O(n * 2^n).

  • Auxiliary space: O(S + n), including the memoization cache, recursion stack, and current path; the worst case is O(2^n + n).

  • Result space: O(kC), potentially O(n * 2^n).

  • Input storage is not counted in the auxiliary-space figure.

Common Pitfalls

  • Incorrect cache key: The key must include every mutable state that affects future choices. Omitting remaining or a relevant used set can return incorrect counts.

  • Caching mutable paths: Store an immutable suffix result or a count, not a shared mutable list. When storing complete paths, append current_path[:].

  • Over-pruning: A branch is safe to remove only when no valid completion can begin there. Use the cached count to prove this.

  • Negative candidates: They are rejected because they can make unbounded combination-sum behavior or recursion difficult to reason about.

  • Duplicate candidates: This implementation collapses equal values. If duplicate multiplicity is meaningful, the state must represent that explicitly.

  • Empty and single-element inputs: A target of 0 returns [[]]; an empty candidate list with a positive target returns []; one candidate is handled normally.

  • Already sorted input: It remains correct because the implementation sorts internally before applying the pruning break.

  • Graph-specific cases: Disconnected graphs and cycles are not applicable here. In graph backtracking, the visited set must be included in or reflected by the memoized state.

12

Why is backtracking important in recursive algorithm design?

Backtracking is a systematic way to explore all possible configurations of a problem by building candidates incrementally and abandoning (backtracking from) partial candidates that cannot lead to a valid solution. It transforms exponential brute-force search into a structured depth-first traversal of the solution space, making problems like permutations, subsets, and constraint satisfaction tractable to implement and reason about.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Idea: Choose / Explore / Un-choose

Backtracking follows a three-step template at each recursion level: 1. Choose – make a decision (add an element to the current path, place a queen, pick a digit). 2. Explore – recurse with the updated state. 3. Un-choose – undo the decision (pop the path, remove the queen, clear the digit) so the caller can try the next option.

This pattern guarantees that every valid combination is visited exactly once while the recursion stack implicitly manages the current partial solution.

State and Base Case

  • State typically includes: path (current partial solution), used or start_index (to avoid duplicates or enforce order), and problem-specific constraints (remaining target sum, board occupancy).

  • Base case is reached when path satisfies the goal (e.g., len(path) == k for combinations, row == n for N-Queens). At that point a copy of path (path[:] or list(path)) is appended to results; never append the mutable path itself.

Pruning: Cutting Branches Early

Pruning stops exploration of a branch the moment it is proven impossible to complete to a valid solution. It is safe because the constraint being checked is monotonic – once violated, adding more choices cannot repair it. - Subsets / combinations: stop when remaining < 0 (combination sum) or len(path) > k. - N-Queens: stop when the new queen attacks any placed queen (column, diagonal). - Sudoku / Word Search: stop when the digit/letter violates row/column/box or board boundaries. Pruning does not change worst-case complexity but dramatically reduces the actual nodes visited.

Search Space Size and Complexity

Problem Search Space (worst case) Time Space (auxiliary)
Subsets 2^n O(n * 2^n) O(n) recursion + O(n * 2^n) output
Permutations n! O(n * n!) O(n) recursion + O(n * n!) output
Combinations (choose k) C(n, k) O(k * C(n, k)) O(k) recursion + output
N-Queens O(n!) (pruned to ~O(2.5^n)) exponential O(n)
Sudoku (m empty cells) 9^m exponential O(m)

All are exponential; backtracking makes the constant factors manageable and the code concise.

When to Use Backtracking

  • The problem asks for all solutions (not just one optimum).

  • Constraints are local and can be checked incrementally.

  • The solution space is a tree or DAG where each level adds one decision.

  • n is small (typically ≤ 15–20 for subsets/permutations, ≤ 9 for N-Queens).

Common Pitfalls and Interview Tips

  • Forgetting to copy the path: results.append(path) stores a reference that later mutates; always use path[:].

  • Missing the un-choose step: leads to corrupted state for sibling branches.

  • Incorrect pruning condition: cutting valid solutions (e.g., remaining < 0 vs remaining <= 0 in combination sum with positive numbers).

  • Not handling duplicates: when input has repeated values, sort and skip if i > start and nums[i] == nums[i-1]: continue.

  • Recursion depth limits: Python defaults to ~1000; for deeper trees (e.g., large sudoku) use an explicit stack or sys.setrecursionlimit.

  • Mutating shared structures: pass copies or restore mutable state (boards, sets) after the recursive call.

  • Draw the recursion tree for a tiny input (e.g., nums = [1,2], k=2) and label choose/explore/un-choose.

  • State the recurrence in words: “At index i, either include nums[i] and recurse with i+1, or skip it and recurse with i+1.”

  • Name the pruning rule explicitly: “We stop when current_sum > target because all numbers are positive.”

  • Follow-up: “How would you return just one solution?” → return True on success and propagate it up. “How to do it iteratively?” → explicit stack holding (path, start_index).

13

How does variable ordering affect backtracking performance?

Variable ordering controls which decision the algorithm makes next, so it can dramatically change how many partial assignments are explored before finding solutions or proving that none exist. A good heuristic chooses constrained variables earlier, allowing conflicts to be detected and pruned sooner.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Why Ordering Matters

Backtracking explores a tree of partial assignments. Although every ordering eventually explores the same solutions when the search is exhaustive, the number of intermediate nodes can differ greatly.

  • Fixed ordering: Select variables according to a predetermined sequence. It is simple and predictable, but an unconstrained variable may be assigned before a highly constrained one.

  • Minimum remaining values (MRV): Select the unassigned variable with the fewest available values. This often detects contradictions earlier.

  • Degree heuristic: Select the variable involved in the most constraints. This is useful when domain sizes are similar.

  • Value ordering: Chooses which value to try for a variable. This is related but separate from variable ordering; a good variable order with poor value ordering can still perform poorly.

Variable ordering generally does not change the theoretical worst-case search space, but it can make practical runtime dramatically better or worse.

Choose, Explore, Un-Choice

A backtracking implementation follows three operations:

  1. Choose: Select the next variable using a fixed or heuristic ordering.

  2. Explore: Try each permitted value and recursively search.

  3. Un-choose: Remove the assignment after exploring its subtree.

The example below models a binary constraint-satisfaction problem where each constraint means two variables must have different values. It prunes a candidate immediately when it conflicts with an already assigned neighbor. This pruning is safe because future assignments cannot change the two conflicting values.

Worked Example

Consider these domains and constraints:

  • A: {0, 1, 2}

  • B: {0}

  • C: {0, 1}

  • A != C

  • B != C

Ordering Decisions Search Nodes Solutions
Fixed A, B, C A, then B, then C 9 2
MRV B, then C, then A 5 2

MRV chooses B because it has one value, then C because it has two values. The fixed ordering first explores A, including branches that later become impossible. Both strategies find the same solutions, but MRV visits fewer nodes.

Code Example

def solve_binary_csp(
    domains: dict[str, frozenset[int]],
    constraints: list[tuple[str, str]],
    order: list[str],
    use_mrv: bool,
) -> tuple[list[dict[str, int]], int]:
    """Solve a binary all-different CSP and report solutions and visited nodes."""
    if len(order) != len(domains) or set(order) != set(domains):
        raise ValueError("order must contain every variable exactly once")

    neighbors: dict[str, list[str]] = {}
    for left, right in constraints:
        neighbors.setdefault(left, []).append(right)
        neighbors.setdefault(right, []).append(left)

    order_index = {variable: index for index, variable in enumerate(order)}
    unassigned = set(domains)
    current: dict[str, int] = {}
    solutions: list[dict[str, int]] = []
    node_count = 0

    def conflicts(variable: str, value: int) -> bool:
        return any(
            neighbor in current and current[neighbor] == value
            for neighbor in neighbors.get(variable, [])
        )

    def backtrack() -> None:
        nonlocal node_count
        node_count += 1

        # BASE CASE: every variable has a value.
        if not unassigned:
            solutions.append(current.copy())
            return

        # CHOOSE: select the next variable.
        if use_mrv:
            variable = min(
                unassigned,
                key=lambda name: (len(domains[name]), order_index[name]),
            )
        else:
            variable = next(name for name in order if name in unassigned)

        for value in sorted(domains[variable]):
            # PRUNE: an assigned conflicting value cannot be repaired later.
            if conflicts(variable, value):
                continue

            # EXPLORE: extend the current partial assignment.
            current[variable] = value
            unassigned.remove(variable)
            backtrack()

            # UN-CHOOSE: restore the state for the next candidate.
            unassigned.add(variable)
            del current[variable]

    backtrack()
    return solutions, node_count


if __name__ == "__main__":
    domains = {
        "A": frozenset({0, 1, 2}),
        "B": frozenset({0}),
        "C": frozenset({0, 1}),
    }
    constraints = [("A", "C"), ("B", "C")]

    fixed_solutions, fixed_nodes = solve_binary_csp(
        domains, constraints, ["A", "B", "C"], False
    )
    mrv_solutions, mrv_nodes = solve_binary_csp(
        domains, constraints, ["A", "B", "C"], True
    )

    print(f"fixed: {len(fixed_solutions)} solutions, {fixed_nodes} nodes")
    print(f"MRV: {len(mrv_solutions)} solutions, {mrv_nodes} nodes")

    # Expected output:
    # fixed: 2 solutions, 9 nodes
    # MRV: 2 solutions, 5 nodes

Complexity

Let n be the number of variables, m the number of constraints, d = max(2, maximum domain size), V the number of visited partial assignments, and S the number of solutions.

  • Best time: O(n(n + m)), when one compatible assignment is found without backtracking. Each level spends O(n) choosing a variable and O(m) checking constraints.

  • Average time: O(V(n + m)), but V is highly instance-dependent, so there is no useful universal average.

  • Worst time: O(d^n(n + m)). The search space is exponential.

  • Auxiliary space: O(n), including the recursion stack, shared assignment, and unassigned-variable set; input is not counted.

  • Result storage: O(Sn) when all solutions are retained.

Common Pitfalls

  • Incorrect restoration: Every explored assignment must be removed before trying the next value.

  • Confusing variable and value ordering: Choosing a better variable does not guarantee a better next value.

  • Assuming a heuristic guarantees optimality: MRV and degree heuristics are practical improvements, not universal guarantees.

  • Ignoring state restoration in recursive helpers: Shared state must be restored in the correct order.

  • Edge cases: An empty CSP returns one empty solution; one-variable problems work normally; duplicate domain values are removed by frozenset; negative integer values are valid; sorted values make value exploration deterministic; disconnected or cyclic constraints require no special handling in this pairwise model.

A common interviewer follow-up is: “Would MRV still help if the problem required enumerating every solution?” The answer is that it usually reduces intermediate nodes and improves runtime, but it does not change the number of final solutions.

14

What is the complexity of a typical backtracking algorithm?

Backtracking complexity depends mainly on the size of the search space: the number of partial solutions explored and the work required at each state. Although its auxiliary space is usually linear in the recursion depth, its running time is commonly exponential or factorial.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Complexity Arises

For a search tree with maximum depth d and average branching factor b:

  • Time: Approximately O(b^d) states. If each state performs w work, the total is O(b^d × w).

  • Auxiliary space: O(d) for the recursion stack and current path, plus O(s) for other maintained state such as a used or visited set.

  • Output space: Counted separately. Storing every solution can dominate total space.

The input itself is not included in the usual auxiliary-space calculation.

For exhaustive, unpruned backtracking, best, average, and worst cases generally have the same asymptotic complexity because the entire search tree is explored. If the algorithm stops after finding the first solution, the best case can be substantially lower.

Typical Search Spaces

Problem Typical worst-case time Auxiliary space Output space
Generate all subsets O(n × 2^n) O(n) Up to O(n × 2^n)
Generate all permutations O(n × n!) O(n) O(n × n!)
N-Queens, row-by-row O(n!) O(n) O(n!) if all solutions are stored
Sudoku with m empty cells O(9^m) O(m) Usually constant-sized output

These are exponential or factorial search spaces. Pruning can greatly improve typical performance, but it does not always improve the worst-case bound.

Common Pitfalls and Interview Tips

  • Appending the path directly: Always use current_path[:]; otherwise later backtracking mutates previously stored results.

  • Forgetting state restoration: Every choose operation needs a matching un-choose operation.

  • Incorrect pruning: Verify that a pruned branch cannot produce any valid result before cutting it off.

  • Ignoring output space: Recursion space may be O(n) while storing all permutations requires O(n × n!).

  • Recursion depth: For search spaces deeper than Python’s default limit of roughly 1,000, use an explicit stack or carefully raised recursion limit.

  • Fixed-width overflow: In languages such as Java or C++, factorial-sized counters can overflow; use an appropriate integer type.

  • Common follow-up: Interviewers often ask how pruning changes typical runtime, whether complexity is output-sensitive, and how duplicates or visited states are handled.

15

How does backtracking's worst case compare with other algorithms?

Backtracking has an exponential or factorial worst case when it explores a combinatorial search tree without effective pruning. Many standard greedy, dynamic-programming, binary-search, and sorting algorithms have polynomial worst cases, although algorithm family alone does not guarantee polynomial complexity; well-pruned backtracking can still outperform unpruned exhaustive search.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Worst-Case Comparison

The following table compares representative algorithms. Backtracking complexity depends on its branching factor and depth; let b be the maximum branching factor and d the maximum search depth.

Approach Best case Average case Worst case Auxiliary space
Backtracking, stopping at first solution O(d) No universal average-case bound; O(b^d) remains an upper bound O(b^d) states, assuming constant work per state Usually O(d)
Backtracking, enumerating all subsets O(n · 2^n) O(n · 2^n) O(n · 2^n) O(n)
Backtracking, enumerating all permutations O(n · n!) O(n · n!) O(n · n!) O(n)
Greedy interval scheduling, including sorting O(n log n) O(n log n) O(n log n) O(n) with a standard comparison sort
Dynamic programming for bounded subset sum O(nS) O(nS) O(nS) O(S)
Binary search on a sorted array O(1) O(log n) O(log n) O(1)

Auxiliary space includes the recursion stack and path state but excludes the input and returned results. For example, enumerating all subsets requires O(n · 2^n) output space when each subset is copied, although its auxiliary working space is only O(n).

Not every alternative to backtracking is polynomial. Held–Karp dynamic programming for the traveling-salesperson problem, for instance, uses O(n² · 2^n) time because its state space is exponential.

Search-Space Growth

Typical backtracking search spaces include:

  • Subsets: O(2^n) decisions, or O(n · 2^n) time when every subset is copied.

  • Permutations: O(n!) states, or O(n · n!) time when every permutation is copied.

  • Combination sum: O(2^n) states for the 0/1 variant; reusable-candidate variants depend on the target and other constraints.

  • Sudoku: up to O(9^m) search states for m empty cells before row, column, and box constraints reduce the tree.

These are exponential or factorial growth rates rather than polynomial bounds. Backtracking is still practical when constraints, input sizes, or strong pruning keep the effective search tree small.

Choose, Explore, Un-Choose

  1. Choose: add a candidate to the current_path and, when needed, a used_set.

  2. Explore: recurse using the updated state and a start_index that prevents inappropriate reuse.

  3. Un-choose: remove the candidate and restore the previous state before trying the next option.

  4. Base case: explicitly recognize when the path is complete, then append current_path.copy() to the results.

Pruning is safe only when it proves that no valid completion exists. An occupied column is invalid in N-Queens. A partial sum greater than the target is a valid cutoff only when all remaining values are non-negative; with negative values, a reachable-value bound is needed. Duplicate choices may be removed when the candidates are equivalent and duplicate outputs are unwanted. Memoization can merge identical states, but it trades additional memory for fewer explorations.

Small Walkthrough

For candidates [A, B], a subset search proceeds as follows:

  1. Begin with current_path = [].

  2. Choose A, producing [A].

  3. Choose B, producing [A, B]; the base case records a copy.

  4. Un-choose B, restoring [A]; the base case records another copy.

  5. Un-choose A, restoring [].

  6. Choose B, producing [B]; the base case records a copy.

  7. Skip B; the base case records the empty subset.

The result contains all 2² subsets, while the working path and recursion stack contain at most two elements.

Common Pitfalls

  • Forgetting to copy paths: Store current_path.copy(); storing the mutable path corrupts earlier results.

  • Off-by-one errors: Define whether the base case is an exact target size, a remaining capacity of zero, or an exhausted index range.

  • Unsafe pruning: Prove that a cutoff cannot discard a feasible completion, especially with duplicates or negative values.

  • Mutating input: Copy or sort a separate sequence when the algorithm changes ordering.

  • Forgetting visited state: Graph and state-space searches need a visited_set to prevent cycles and repeated exploration.

  • Ignoring edge cases: Clarify behavior for empty input, one element, duplicates, negative values, and already sorted input.

  • Overflow and recursion depth: Python integers do not overflow, but exponential counts can exceed fixed-width integer limits in other languages. Large recursive searches can also exceed Python’s recursion limit and may require an explicit stack.

  • Common follow-up: Interviewers often ask how to prove pruning safe, convert the search to dynamic programming with memoization, or estimate complexity for a specific constraint size.

16

How do you solve N-Queens using backtracking?

Backtracking solves N-Queens by placing one queen per row, exploring each legal column, and undoing a choice whenever it cannot lead to a valid arrangement. Column and diagonal bitmasks identify conflicting positions immediately.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Backtracking State

The recursive search maintains:

  • current path: the selected column for the queen in each row.

  • columns: columns that already contain a queen.

  • left diagonals and right diagonals: columns attacked diagonally in the next row.

  • base case: after placing a queen in all n rows, save the completed board.

The algorithm follows the choose / explore / un-choose pattern:

  1. Choose an unattacked column for the current row.

  2. Explore that placement recursively.

  3. Un-choose the queen before trying another column.

Safe Pruning

A candidate column is removed from consideration if it is occupied by another queen or attacked diagonally. This pruning is safe because a queen already placed in an earlier row cannot be moved later, so every continuation from that placement would also be invalid.

Bitmasks make each conflict check constant-time under the usual machine-word assumption.

Small Example

For n = 4, starting in row 0:

  1. Column 0 leads only to dead ends: every placement in rows 1 and 2 leaves no safe column in a later row.

  2. Column 1 allows a queen in row 1, column 3.

  3. Row 2 can then use column 0.

  4. The final queen goes in row 3, column 2.

This produces the board:

.Q..
...Q
Q...
..Q.

Complexity

Let S be the number of valid solutions.

  • Search space: O(n!), corresponding to the possible row-by-row column placements. This is factorial rather than merely exponential.

  • Time:

  • Best: O(n) for the trivial cases n <= 1.

  • Average and worst: O(n! + S × n). The first term covers the search, and the second covers constructing all returned boards. Diagonal pruning improves practical runtime, although both cases have the same asymptotic upper bound.

  • Auxiliary space: O(n), including the recursion stack and current_path. The scalar input is not counted.

  • Output space: O(S × n) for all completed boards.

Code Example

def n_queens(n: int) -> list[list[str]]:
    """Return every valid placement of n non-attacking queens."""
    if n < 0:
        raise ValueError("n must be non-negative")

    full_mask = (1 << n) - 1
    solutions: list[list[str]] = []
    current_path: list[int] = []

    def search(
        columns: int,
        left_diagonals: int,
        right_diagonals: int,
    ) -> None:
        row = len(current_path)

        # Base case: one queen has been placed in every row.
        if row == n:
            solutions.append([
                "".join(
                    "Q" if current_path[row] == column else "."
                    for column in range(n)
                )
                for row in range(n)
            ])
            return

        available = full_mask & ~(
            columns | left_diagonals | right_diagonals
        )

        while available:
            # Select and remove the lowest available column bit.
            queen_bit = available & -available
            available ^= queen_bit
            column = queen_bit.bit_length() - 1

            # Choose: add this queen to the current path.
            current_path.append(column)

            # Explore: recurse with the new column and diagonal attacks.
            search(
                columns | queen_bit,
                (left_diagonals | queen_bit) << 1,
                (right_diagonals | queen_bit) >> 1,
            )

            # Un-choose: restore the state before trying another column.
            current_path.pop()

    search(columns=0, left_diagonals=0, right_diagonals=0)
    return solutions


print(n_queens(4))
# Expected: [['.Q..', '...Q', 'Q...', '..Q.'], ['..Q.', 'Q...', '...Q', '.Q..']]

Edge Cases and Common Pitfalls

  • Empty input: n_queens(0) returns one empty board, [[]].

  • One element: n_queens(1) returns [["Q"]].

  • No solution: n_queens(2) and n_queens(3) both return []; n = 4 is the smallest board above 1 with solutions (two).

  • Invalid size: negative n raises ValueError.

  • Duplicates: impossible because only one column is selected per row, and the column mask prevents another queen from sharing it.

  • Mutation: always remove current_path.pop() during backtracking; otherwise earlier choices incorrectly affect later branches.

  • Recursion depth: the recursion depth is n. Very large boards require an explicit stack or a safely increased recursion limit.

17

How do you solve a Sudoku puzzle with backtracking?

Backtracking solves Sudoku by filling one empty cell at a time with a legal digit, recursively exploring that choice, and undoing it when the remaining cells cannot be completed. The algorithm stops when every empty cell has a valid assignment.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The solver maintains the puzzle board and three sets of used digits:

  • row_used[row]: digits already present in a row.

  • col_used[col]: digits already present in a column.

  • box_used[box]: digits already present in a 3×3 box.

The box index is (row // 3) * 3 + (col // 3).

The state consists of the empty_cells list, the current index, the board, and the three used-digit sets. The assignments on the current recursion path act as the current path.

For each empty cell, the solver:

  1. Chooses a digit from 1 through 9 that does not conflict with its row, column, or box.

  2. Explores the remaining puzzle recursively.

  3. Unchooses the digit by removing it from the sets and restoring the cell to 0.

The base case is index == len(empty_cells): every empty cell has then been assigned.

Pruning and Walkthrough

A candidate that conflicts with its row, column, or box can never lead to a valid completion, so rejecting it immediately is safe.

In the full 9×9 puzzle used in the code below, the first empty cell is (0, 2), and its legal candidates are {1, 2, 4}.

Step Action
1 Select cell (0, 2) and try digit 1.
2 Recursively solve the remaining empty cells.
3 If that branch fails, remove 1 and restore the cell to 0.
4 Try the next legal digit, such as 2 or 4.
5 Continue until a valid board is found or every candidate fails.

This is the choose / explore / un-choose backtracking pattern.

Complexity

Let m be the number of initially empty cells.

Approach Time Auxiliary Space When to Use
Unpruned brute force O(9^m) O(m) Baseline or very small puzzles
Row, column, and box checks O(9^m) worst case O(m + 81) Typical interview solution
Constraint propagation plus backtracking O(9^m) worst-case bound O(m + 81) Difficult or highly constrained puzzles
  • Best case: O(81 + m) when the puzzle is already solved or no assignment needs to be undone.

  • Average case: A meaningful average requires a specified input distribution; O(9^m) is a conservative general bound, while actual work is usually lower because of pruning.

  • Worst case: O(9^m). The search space is exponential because each empty cell can initially require testing up to nine digits.

  • Auxiliary space: O(m + 81) = O(m + 1), including the recursion stack, empty_cells, and used-digit sets. The input board is not counted; because the board is always 9×9, total memory is effectively constant.

Code Example

def solve_sudoku(board: list[list[int]]) -> bool:
    """Solve a 9x9 Sudoku board in place and report whether it is solvable."""
    if len(board) != 9 or any(len(row) != 9 for row in board):
        return False

    row_used: list[set[int]] = [set() for _ in range(9)]
    col_used: list[set[int]] = [set() for _ in range(9)]
    box_used: list[set[int]] = [set() for _ in range(9)]
    empty_cells: list[tuple[int, int]] = []

    # Validate the initial clues and collect the empty cells.
    for row in range(9):
        for col in range(9):
            value = board[row][col]

            if (
                isinstance(value, bool)
                or not isinstance(value, int)
                or not 0 <= value <= 9
            ):
                return False

            box = (row // 3) * 3 + (col // 3)

            if value == 0:
                empty_cells.append((row, col))
            else:
                if (
                    value in row_used[row]
                    or value in col_used[col]
                    or value in box_used[box]
                ):
                    return False

                row_used[row].add(value)
                col_used[col].add(value)
                box_used[box].add(value)

    def backtrack(index: int) -> bool:
        # Base case: every empty cell has been assigned.
        if index == len(empty_cells):
            return True

        row, col = empty_cells[index]
        box = (row // 3) * 3 + (col // 3)

        for digit in range(1, 10):
            if (
                digit in row_used[row]
                or digit in col_used[col]
                or digit in box_used[box]
            ):
                continue

            # Choose: place the digit and update the used-digit sets.
            board[row][col] = digit
            row_used[row].add(digit)
            col_used[col].add(digit)
            box_used[box].add(digit)

            # Explore: recursively solve the remaining cells.
            if backtrack(index + 1):
                return True

            # Unchoose: restore the state before trying another digit.
            row_used[row].remove(digit)
            col_used[col].remove(digit)
            box_used[box].remove(digit)
            board[row][col] = 0

        return False

    return backtrack(0)


example = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9],
]

result = solve_sudoku(example)
print(result)
# Expected output: True

Common Pitfalls

  • Mutating the input: This implementation solves board in place; copy it if the original must remain unchanged.

  • Invalid dimensions or values: Empty boards, one-element boards, negative values, values outside 0 through 9, and booleans are rejected.

  • Duplicate clues: Conflicting nonzero digits in a row, column, or box return False.

  • Unsolvable puzzles: The function returns False and restores the board to its original empty-cell state.

  • Already solved puzzles: A valid completed board returns True without changes.

  • Sorted input: There is no distinct sorted-input case for Sudoku; clue order does not affect correctness.

  • Forgetting to undo choices: Failure to remove a digit from all three sets causes incorrect pruning.

  • Box indexing errors: The formula must distinguish all nine boxes.

  • Graph cases: Disconnected components and cycles do not apply to Sudoku.

  • Common follow-up: Choosing the empty cell with the fewest candidates, or adding constraint propagation, often reduces the search considerably.

18

How do you solve the rat in a maze problem with backtracking?

Backtracking explores each possible path from the starting cell, records the current route, and undoes choices that cannot reach the destination. It finds a path by depth-first search while pruning walls, invalid positions, and revisited cells.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Approach

Assume the maze is a rectangular matrix where 1 represents an open cell and 0 represents a wall. The rat starts at the top-left cell and must reach the bottom-right cell, moving up, down, left, or right.

For each recursive call:

  1. Choose: Add the current cell to the path and mark it as used.

  2. Explore: Try every valid neighboring cell.

  3. Un-choose: If a branch fails, remove the current cell so another route can use it.

  4. At the destination, copy the current path into the results.

The recursive state consists of the current cell, the current_path, and the used set. The start_index remains fixed at (0, 0).

Pruning and Backtracking

A candidate cell is discarded when it is:

  • Outside the maze boundaries.

  • A wall containing 0.

  • Already present in the used set.

These cuts are safe because a valid path cannot leave the grid, pass through a wall, or revisit a cell. The used set prevents infinite exploration in mazes containing cycles.

Example Walkthrough

For this maze:

1 1 0 1
1 1 0 0
1 0 0 0
1 1 1 1
  1. Start at (0, 0) and choose it.

  2. Move down through (1, 0) and (2, 0).

  3. Move to (3, 0), then right through (3, 1) and (3, 2).

  4. Reach the destination at (3, 3) and save a copy of the path.

  5. Undo each choice while returning from the recursion.

Complexity

Let R be the number of rows and C the number of columns.

Case Time Reason
Best O(RC) The destination is reached directly along a path of at most RC cells.
Average O(4^(RC)) conservative upper bound Maze connectivity affects how many routes are explored; the search remains potentially exponential.
Worst O(4^(RC)) Each recursive level has at most four choices, and a simple path can contain RC cells. The search space is exponential.

Auxiliary space: O(RC), including the recursion stack, current_path, used set, and saved result. The input matrix is not counted separately.

Code Example

def solve_rat_in_maze(maze: list[list[int]]) -> list[tuple[int, int]] | None:
    """Return a path from the top-left to the bottom-right, or None."""
    if not maze:
        return None

    rows = len(maze)
    columns = len(maze[0])

    if columns == 0:
        return None
    if any(len(row) != columns for row in maze):
        raise ValueError("The maze must be rectangular.")
    if any(cell not in (0, 1) for row in maze for cell in row):
        raise ValueError("Maze cells must be 0 or 1.")

    start_index = (0, 0)
    destination = (rows - 1, columns - 1)

    if maze[0][0] == 0 or maze[destination[0]][destination[1]] == 0:
        return None

    current_path: list[tuple[int, int]] = []
    used: set[tuple[int, int]] = set()
    results: list[list[tuple[int, int]]] = []
    directions = ((1, 0), (0, 1), (-1, 0), (0, -1))

    def backtrack(row: int, column: int) -> bool:
        position = (row, column)

        # Choose: add this cell to the current route.
        current_path.append(position)
        used.add(position)

        # Base case: the destination was chosen.
        found = position == destination

        if found:
            # Save a copy of the path before backtracking undoes it.
            results.append(current_path[:])

        if not found:
            # Explore each unvisited, open neighboring cell.
            for row_change, column_change in directions:
                next_row = row + row_change
                next_column = column + column_change

                if not (0 <= next_row < rows and 0 <= next_column < columns):
                    continue
                if maze[next_row][next_column] == 0:
                    continue
                if (next_row, next_column) in used:
                    continue

                if backtrack(next_row, next_column):
                    found = True
                    break

        # Un-choose: restore state before exploring another route.
        current_path.pop()
        used.remove(position)

        return found

    backtrack(*start_index)
    return results[0] if results else None


maze = [
    [1, 1, 0, 1],
    [1, 1, 0, 0],
    [1, 0, 0, 0],
    [1, 1, 1, 1],
]

print(solve_rat_in_maze(maze))
# [(0, 0), (1, 0), (2, 0), (3, 0), (3, 1), (3, 2), (3, 3)]

Edge Cases

  • Empty maze: Returns None.

  • One-cell maze: Returns that cell when it is open.

  • Blocked start or destination: Returns None.

  • Disconnected maze: Returns None after exhausting all routes.

  • Cycles: The used set prevents repeated cells.

  • Ragged matrix or values other than 0 and 1: Raises ValueError.

  • Duplicate values, negative values, and sorted input are not meaningful for a binary maze matrix.

Common Pitfalls

  • Appending the same path object: Use current_path[:] so later backtracking does not change the saved result.

  • Forgetting to restore state: Both current_path and used must be updated during un-choosing.

  • Marking cells visited permanently: A visited cell may be needed on a different route; undo visits during backtracking.

  • Ignoring boundaries or walls: Check both before recursing.

  • Excessive recursion depth: The stack can reach RC levels. For mazes with more than roughly 1,000 cells on a possible path, use an explicit stack or carefully raise Python’s recursion limit.

  • Mutating the input unnecessarily: The matrix can remain unchanged; track visited cells separately.

19

How does backtracking generate all string permutations in Python?

Backtracking generates permutations by choosing one unused character at a time, recursively exploring that choice, and then undoing it to consider other choices. The implementation below returns every distinct permutation exactly once, even when the input contains repeated characters.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The recursive state consists of:

  • Current path: The characters selected for the permutation currently being constructed.

  • Remaining counts: How many copies of each character are still available.

  • Results: Completed permutations stored as strings.

The base case occurs when len(current_path) == len(text). At that point, the current path is complete and is added to the results.

For example, with "aab":

Step Current path Remaining counts Result
Choose a a a: 1, b: 1 —
Choose a aa a: 0, b: 1 —
Choose b aab a: 0, b: 0 "aab"
Undo choices, then choose b b a: 2, b: 0 —
Choose a, then a baa a: 0, b: 0 "baa"

Exploring all valid continuations produces "aab", "aba", and "baa".

Pruning and State Management

The algorithm uses the standard choose → explore → un-choose pattern:

  1. Choose a character whose remaining count is positive.

  2. Explore all permutations that begin with the extended path.

  3. Un-choose the character by restoring its count and removing it from the path.

Pruning occurs when a character has no remaining copies. Such a branch cannot produce a valid permutation and is therefore skipped safely. Using character counts also prevents duplicate permutations caused by repeated characters.

Complexity

Let n be the string length and P the number of distinct permutations.

Case Time Reason
Best O(n) All characters are identical, so only one path is explored.
Average O(nP) Each of the P results contains n characters, and the recursive search performs work proportional to those branches.
Worst O(n × n!) All characters are distinct, producing n! permutations, each requiring O(n) time to construct.

The search space is factorial—often described as exponential—with up to n! leaves.

  • Auxiliary space: O(n), including the recursion stack, current path, and remaining counts. The input and returned results are not counted.

  • Output space: O(nP), because each of the P permutations contains n characters.

  • Total space: O(nP + n) when the output is included.

Code Example

from collections import Counter


def generate_permutations(text: str) -> list[str]:
    """Return all distinct permutations of text using backtracking."""
    # State: characters still available and the current path.
    remaining_counts: Counter[str] = Counter(text)
    current_path: list[str] = []
    results: list[str] = []

    def backtrack() -> None:
        # Base case: the current path is a complete permutation.
        if len(current_path) == len(text):
            results.append("".join(current_path))
            return

        for character in remaining_counts:
            if remaining_counts[character] == 0:
                continue

            # Choose: use one available copy of the character.
            remaining_counts[character] -= 1
            current_path.append(character)

            # Explore: generate permutations containing this choice.
            backtrack()

            # Un-choose: restore the previous state.
            current_path.pop()
            remaining_counts[character] += 1

    backtrack()
    return results


print(generate_permutations("aab"))  # ['aab', 'aba', 'baa']

Common Pitfalls

  • Duplicate outputs: Counting the remaining copies of each character, as above, suppresses duplicate permutations. Tracking used positions instead would let repeated characters produce duplicate strings unless equal characters are skipped at the same level.

  • Mutable results: Do not append current_path directly. Appending "".join(current_path) creates an independent completed string.

  • Missing restoration: Every recursive choice must be undone; otherwise later branches receive an invalid state.

  • Empty input: The function returns [""], representing the one permutation of an empty sequence.

  • One character: The function returns ["x"].

  • Input order: Results are not required to be lexicographically sorted; sorting the input would be needed only for deterministic lexicographic output.

  • Deep recursion: For strings longer than roughly 1,000 characters, Python’s recursion limit may need to be raised or the algorithm converted to an explicit stack.

20

How do you implement backtracking for the subset sum problem?

A backtracking solution for the subset sum problem builds a candidate subset by choosing or skipping elements while tracking the sum still needed. This implementation returns all distinct value combinations whose elements sum to the target.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The algorithm maintains four important pieces of state:

  • path: the elements currently chosen.

  • remaining: the sum still needed to reach target.

  • start_index: the next input position that may be selected.

  • used_indices: the positions currently included in path.

At each position, it makes a binary decision:

  1. Choose the current element and add it to the path.

  2. Explore the recursive state after that choice.

  3. Un-choose the element before considering the alternative.

  4. Skip the current element and continue with the next position.

The base case occurs when start_index reaches the end of the input. A solution is recorded whenever remaining == 0. The algorithm does not return immediately at that point because zero or negative elements could extend the current subset into another valid combination.

Pruning and Duplicate Handling

Two optimizations are used:

  • Negative-remainder pruning: If every input value is nonnegative, a negative remaining cannot be repaired by later elements, so that branch is cut off.

  • Duplicate-result removal: Results are stored as tuples in seen_results, so repeated input values do not produce duplicate combinations.

No “remaining sum is too large” pruning is applied when negative numbers are present, because a later negative value could make the branch valid.

Complexity

The search space contains up to 2^n subsets, so the algorithm is exponential.

Case Time Space Reason
Best O(n) O(n) A root-level impossibility check may reject the target immediately.
Typical O(2^n) search O(n) auxiliary Each binary decision explores a subset state.
Worst O(n · 2^n) O(n · S) including results Results are copied and deduplicated; S is the number of returned combinations.

Auxiliary space includes the recursion stack, current path, used-index set, and sorted copy. The original input is not counted; the sorted copy is counted. For comparison, a dynamic-programming solution for nonnegative integers with a bounded target T takes O(nT) time and O(T) space, but it is less suitable for negative values or very large targets.

Example Walkthrough

For numbers = [1, 2, 3] and target = 3:

  1. Choose 1; remaining becomes 2.

  2. Choose 2; remaining becomes 0, so [1, 2] is recorded.

  3. Backtrack and skip 2.

  4. Backtrack past 1, then choose 3; remaining becomes 0, so [3] is recorded.

The result is [[1, 2], [3]].

Code Example

def subset_sum(numbers: list[int], target: int) -> list[list[int]]:
    """Return distinct value combinations whose sum equals target."""
    values = sorted(numbers)
    results: list[list[int]] = []
    seen_results: set[tuple[int, ...]] = set()
    path: list[int] = []
    used_indices: set[int] = set()
    all_nonnegative = all(value >= 0 for value in values)

    def backtrack(start_index: int, remaining: int) -> None:
        # Base case: record a complete path when the target is reached.
        if remaining == 0:
            result = tuple(path)
            if result not in seen_results:
                seen_results.add(result)
                results.append(path.copy())

        if start_index == len(values):
            return

        # Safe pruning only when later values cannot reduce the sum.
        if all_nonnegative and remaining < 0:
            return

        value = values[start_index]

        # Choose the current element.
        path.append(value)
        used_indices.add(start_index)

        # Explore the choice.
        backtrack(start_index + 1, remaining - value)

        # Un-choose the current element.
        used_indices.remove(start_index)
        path.pop()

        # Explore the alternative of skipping the current element.
        backtrack(start_index + 1, remaining)

    backtrack(0, target)
    return results


print(subset_sum([1, 2, 3], 3))  # [[1, 2], [3]]

Common Pitfalls and Interview Tips

  • Do not mutate the input: Sorting a copy keeps the caller’s list unchanged.

  • Copy results: Use path.copy(), not path, or later backtracking will change previously recorded solutions.

  • Handle duplicates deliberately: This version returns distinct value combinations; index-based implementations may treat equal elements as different choices.

  • Support negative numbers: Avoid pruning based only on remaining < 0 unless all remaining values are nonnegative.

  • Explain the base case clearly: It is reached when there are no input positions left to choose.

  • Common follow-up: Compare this exponential search with dynamic programming, meet-in-the-middle, or integer-programming approaches.

21

How can backtracking solve the Crossword Puzzle problem?

Backtracking solves the Crossword Puzzle problem by assigning a word to one crossword slot at a time, exploring alternatives whenever a placement conflicts with already-filled letters. A choose / explore / un-choose process preserves completed assignments until the recursive branch fails.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Backtracking Model

The search state consists of:

  • Current path: current_path, containing the placements made so far.

  • Used set: used_entries, ensuring each supplied entry is used once.

  • Start index: start_index, identifying the next slot to fill.

  • Base case: start_index == len(slots), meaning every slot has been filled successfully.

For each slot, the algorithm:

  1. Choose an unused word with the correct length that matches existing letters.

  2. Explore the placement recursively.

  3. Un-choose it if the recursive call fails, restoring both the board and the path.

The implementation uses . for an empty cell, # for a blocked cell, and uppercase letters for prefilled cells.

Pruning and State

A candidate word is rejected immediately when:

  • It has the wrong length.

  • Its entry has already been used.

  • It disagrees with a prefilled letter.

  • It disagrees with a crossing word placed earlier.

If a slot has no candidates, the current branch is cut off because no valid completion can begin with that state. This pruning is safe because every invalid assignment is rejected without exploring its descendants.

The slot order can be improved by trying longer or more constrained slots first. In this implementation, slots are sorted by descending length before recursion.

Example Walkthrough

Using the example from the code:

Grid: Row 0: # . . # Row 1: # # # #

Entries: [(“AT”, “A small city”)]

Steps: 1. Slot detection: _find_slots scans rows and columns. It finds one across slot at row 0, columns 1–2 (cells (0,1) and (0,2)). No down slots of length ≥2. Slots list = [Slot(“across”, 0, 1, ((0,1),(0,2)))]. 2. Validation: Number of slots (1) equals number of entries (1). Board becomes [['#','.', '.', '#'], ['#','#','#','#']]. 3. Search start: search(0) called with start_index=0. 4. Compatible words: For the slot, compatible_words checks entry 0 (“AT”). Length matches (2). Board cells are both ‘.’, so compatible. Candidates = [0]. 5. Choose: Place “AT”: board[0][1]=‘A’, board[0][2]=‘T’; changed_cells = [(0,1),(0,2)]; used_entries = {0}; current_path = [Placement(“AT”, “A small city”, “across”, 0, 1, ((0,1),(0,2)))]. 6. Explore: Recursive call search(1). start_index == len(slots) (1 == 1) → base case true, returns True. 7. Un-choose not needed because solution found. The recursion unwinds returning True. 8. Result: solve_crossword returns sorted current_path → [Placement(word=‘AT’, clue=‘A small city’, direction=‘across’, row=0, col=1, cells=((0,1),(0,2)))].

Code Example

from dataclasses import dataclass


@dataclass(frozen=True)
class Slot:
    direction: str
    row: int
    col: int
    cells: tuple[tuple[int, int], ...]


@dataclass(frozen=True)
class Placement:
    word: str
    clue: str
    direction: str
    row: int
    col: int
    cells: tuple[tuple[int, int], ...]


def _find_slots(grid: list[str]) -> list[Slot]:
    """Find maximal across/down slots containing at least one empty cell."""
    slots: list[Slot] = []
    rows = len(grid)
    cols = len(grid[0]) if rows else 0

    for row in range(rows):
        col = 0
        while col < cols:
            if grid[row][col] == "#":
                col += 1
                continue

            start = col
            while col < cols and grid[row][col] != "#":
                col += 1

            cells = tuple((row, position) for position in range(start, col))
            if len(cells) >= 2 and any(
                grid[r][c] == "." for r, c in cells
            ):
                slots.append(Slot("across", row, start, cells))

    for col in range(cols):
        row = 0
        while row < rows:
            if grid[row][col] == "#":
                row += 1
                continue

            start = row
            while row < rows and grid[row][col] != "#":
                row += 1

            cells = tuple((position, col) for position in range(start, row))
            if len(cells) >= 2 and any(
                grid[r][c] == "." for r, c in cells
            ):
                slots.append(Slot("down", start, col, cells))

    return sorted(slots, key=lambda slot: (-len(slot.cells), slot.row, slot.col))


def solve_crossword(
    grid: list[str],
    entries: list[tuple[str, str]],
) -> list[Placement]:
    """Solve a crossword grid using words and clues; return [] if unsolvable."""
    if not grid or any(len(row) != len(grid[0]) for row in grid):
        raise ValueError("Grid rows must have equal, non-zero length")

    slots = _find_slots(grid)
    if len(slots) != len(entries):
        raise ValueError("The number of entries must equal the number of slots")

    board = [list(row.upper()) for row in grid]
    normalized_entries = [
        (word.upper(), clue) for word, clue in entries
    ]

    current_path: list[Placement] = []
    used_entries: set[int] = set()

    def compatible_words(slot: Slot) -> list[int]:
        candidates: list[int] = []

        for entry_index, (word, _) in enumerate(normalized_entries):
            if entry_index in used_entries:
                continue
            if len(word) != len(slot.cells):
                continue

            if all(
                board[row][col] == "." or board[row][col] == letter
                for (row, col), letter in zip(slot.cells, word)
            ):
                candidates.append(entry_index)

        return candidates

    def search(start_index: int) -> bool:
        # Base case: every slot has been assigned.
        if start_index == len(slots):
            return True

        slot = slots[start_index]
        candidates = compatible_words(slot)

        for entry_index in candidates:
            word, clue = normalized_entries[entry_index]
            changed_cells: list[tuple[int, int]] = []

            # Choose: place the word in the current slot.
            for (row, col), letter in zip(slot.cells, word):
                if board[row][col] == ".":
                    board[row][col] = letter
                    changed_cells.append((row, col))

            used_entries.add(entry_index)
            current_path.append(
                Placement(
                    word,
                    clue,
                    slot.direction,
                    slot.row,
                    slot.col,
                    slot.cells,
                )
            )

            # Explore: recursively fill the remaining slots.
            if search(start_index + 1):
                return True

            # Un-choose: restore the board and search state.
            current_path.pop()
            used_entries.remove(entry_index)
            for row, col in changed_cells:
                board[row][col] = "."

        return False

    if search(0):
        return sorted(
            current_path,
            key=lambda placement: (
                placement.row,
                placement.col,
                placement.direction,
            ),
        )
    return []


if __name__ == "__main__":
    grid = ["#..#", "####"]
    entries = [("AT", "A small city")]

    print(solve_crossword(grid, entries))

# Output:
# [Placement(word='AT', clue='A small city', direction='across',
#            row=0, col=1, cells=((0, 1), (0, 2)))]

Complexity

Let S be the number of slots and entries, L the maximum slot length, and R × C the grid size.

  • Best time: O(S²L). Every slot is filled without backtracking, but each level scans up to S candidate words and compares up to L letters.

  • Average time: data-dependent and bounded between the best and worst cases. Effective length, crossing, and used-word pruning can substantially reduce the search.

  • Worst time: O(S! · S · L). There are at most S! word-to-slot assignments, and each search node checks candidate compatibility. This search space is factorial, not polynomial.

  • Auxiliary space: O(RC + S² + SL), including the copied grid, recursion stack, per-level candidate lists, and stored placements, but excluding the original input. Counting the input adds O(RC + S).

Common Pitfalls

  • Failing to undo every modified cell: Restore only cells changed by the current placement.

  • Reusing an entry: Track used entries separately from the board state.

  • Ignoring crossings: Check every already-filled cell, including prefilled letters.

  • Mutating the caller’s grid: Work on a copied board.

  • Incorrect slot detection: Ensure that across and down slots are not accidentally duplicated.

  • Interview follow-up: Interviewers commonly ask about improving pruning, handling multiple solutions, supporting duplicate words, and replacing recursive backtracking with an explicit stack when the number of slots is very large.

22

How do I implement a Word Search solver with backtracking?

Backtracking solves Word Search by exploring possible paths from each matching starting cell and backtracking whenever a path cannot form the target word. It tracks both the current path and the cells already used so that no cell appears twice in the same path.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The solver starts a search at every cell containing the first character of the word. From each position, it explores the eight adjacent directions: horizontal, vertical, and diagonal.

For every candidate cell, it performs three operations:

  1. Choose: Mark the cell as used and append its coordinates to the current path.

  2. Explore: Continue recursively if the cell matches the next required character.

  3. Un-choose: If the branch fails, remove the cell from the path and mark it unused.

Pruning is safe because a valid path cannot include a cell that is outside the grid, already used, or contains the wrong character.

Example walkthrough

For this grid and the word ABCE:

A B
C E
  1. Start at A at (0, 0) and choose it.

  2. Explore adjacent B at (0, 1) and choose it.

  3. Explore C at (1, 0), diagonally adjacent to B, and choose it.

  4. Explore adjacent E at (1, 1), completing the word.

The returned path is [(0, 0), (0, 1), (1, 0), (1, 1)].

Complexity

Let R be the number of rows, C the number of columns, and L the word length.

Case Time Reason
Best O(RCL) The first attempted path succeeds after matching all characters.
Average Data-dependent; O(RC · 7^L) remains the general upper bound Character mismatches and boundary checks prune most branches on typical inputs.
Worst O(RC · 7^L) There are RC starting positions, and each path has exponential branching.

The search space is exponential, approximately O(RC · 7^L): with eight directions, the first step has at most eight neighbors, while later steps have at most seven because the previous cell is already used. (The classic four-direction version is O(RC · 3^L).)

Space complexity is O(RC + L), excluding the input, for the used matrix, current path, and recursion stack. Including the input, it remains O(RC + L).

Code Example

def find_word(
    grid: list[list[str]],
    word: str,
) -> list[tuple[int, int]] | None:
    """Return the coordinates of a word path, or None if no path exists."""
    if not word or not grid or not grid[0]:
        return None

    rows = len(grid)
    cols = len(grid[0])

    if any(len(row) != cols for row in grid):
        raise ValueError("grid must be rectangular")

    if len(word) > rows * cols:
        return None

    directions = (
        (-1, -1), (-1, 0), (-1, 1),
        (0, -1),           (0, 1),
        (1, -1),  (1, 0),  (1, 1),
    )

    used = [[False] * cols for _ in range(rows)]
    current_path: list[tuple[int, int]] = []

    def backtrack(
        current_row: int,
        current_col: int,
        start_index: int,
    ) -> list[tuple[int, int]] | None:
        # Choose: add this cell to the current path and used cells.
        used[current_row][current_col] = True
        current_path.append((current_row, current_col))

        # Base case: every character in the word has been matched.
        if start_index == len(word) - 1:
            return current_path[:]

        next_character = word[start_index + 1]

        # Explore each adjacent matching, unused cell.
        for row_delta, col_delta in directions:
            next_row = current_row + row_delta
            next_col = current_col + col_delta

            if not (0 <= next_row < rows and 0 <= next_col < cols):
                continue
            if used[next_row][next_col]:
                continue
            if grid[next_row][next_col] != next_character:
                continue

            result = backtrack(next_row, next_col, start_index + 1)
            if result is not None:
                return result

        # Un-choose: restore the state before this branch.
        used[current_row][current_col] = False
        current_path.pop()
        return None

    for start_row in range(rows):
        for start_col in range(cols):
            if grid[start_row][start_col] != word[0]:
                continue

            result = backtrack(start_row, start_col, 0)
            if result is not None:
                return result

    return None


if __name__ == "__main__":
    board = [
        ["A", "B"],
        ["C", "E"],
    ]

    path = find_word(board, "ABCE")
    print(path)
    # [(0, 0), (0, 1), (1, 0), (1, 1)]

Edge Cases

  • Empty grid or empty word: Returns None.

  • One-character word: Returns the coordinates of the first matching cell.

  • Duplicate letters: Treated as separate characters, but the same cell cannot be reused within one path.

  • Word longer than the number of cells: Returns None without searching.

  • No valid path: Returns None.

  • Ragged grid: Raises ValueError because rows must have equal lengths.

  • Negative numbers, sorted input, and disconnected graphs: Not applicable to this puzzle.

Common Pitfalls

  • Forgetting to un-choose: A failed branch would incorrectly block cells in later branches.

  • Reusing a cell: Always check used; preventing repeated cells also prevents search cycles.

  • Incorrect indexing: The base case occurs when start_index == len(word) - 1.

  • Mutating the input: This implementation leaves grid unchanged and returns a copy of the path.

  • Deep recursion: The recursive version uses one stack frame per matched character. For words longer than roughly 1,000 characters, use an explicit stack or raise Python’s recursion limit.

23

How do you solve graph coloring with backtracking?

Graph coloring backtracking assigns colors to vertices incrementally and explores alternative assignments whenever a color conflicts with an already colored neighbor. The implementation below solves the decision problem: can an undirected graph be colored using at most k colors?

Read full answer

Applies toPython 3.12

How It Works

The backtracking state consists of:

  • position: the index of the next vertex to color.

  • assignment: the partial mapping from vertices to colors.

  • Base case: every vertex has a color, so a complete valid coloring has been found.

  • Choose: assign a valid color to the current vertex.

  • Explore: recursively color the remaining vertices.

  • Unchoose: remove the assignment if the recursive call fails, then try another color.

Vertices are processed in descending degree order. This does not change correctness, but it often exposes conflicts earlier and reduces the search tree.

Conflict pruning is safe because two adjacent vertices with the same color already form an invalid edge. Coloring later vertices cannot repair that conflict, so the entire branch is discarded.

For the path 0 — 1 — 2 — 3, the search proceeds as follows:

Step Vertex Assignment Reason
1 1 1 = 0 First vertex receives the first available color
2 2 2 = 1 Color 0 conflicts with vertex 1
3 0 0 = 1 Color 0 conflicts with vertex 1
4 3 3 = 0 Only adjacent colored vertex is 2, which has color 1

Complexity

Let n be the number of vertices, m the number of edges, and k the available colors. The search space contains up to O(k^n) color assignments, which is exponential.

Approach Best time Average time Worst time Space When to use
Unpruned enumeration O(n·k^n) O(n·k^n) O(n·k^n) O(n) additional Small instances when every assignment must be checked
Backtracking with pruning O(n+m) O(n·k^n) conservative bound O(n·k^n) O(n+m) total General practical solution with early conflict pruning

The best case occurs when no backtracking is needed: construction and coloring take O(n+m). A meaningful average requires a distribution over graphs; for difficult dense or unsatisfiable instances, runtime commonly approaches the worst case.

Space is O(n+m) total, including the input, generated adjacency sets, partial assignment, and the O(n) recursion stack. The input itself is included in this count.

Code Example

def solve_graph_coloring(
    vertices: list[int],
    edges: list[tuple[int, int]],
    colors: int,
) -> dict[int, int] | None:
    """Return a proper coloring using colors 0..colors-1, or None."""
    if colors <= 0:
        raise ValueError("colors must be positive")

    vertex_set = set(vertices)
    if len(vertex_set) != len(vertices):
        raise ValueError("vertices must contain unique identifiers")

    adjacency: dict[int, set[int]] = {vertex: set() for vertex in vertices}

    for left, right in edges:
        if left not in vertex_set or right not in vertex_set:
            raise ValueError("every edge endpoint must be a known vertex")
        if left == right:
            return None  # A self-loop makes proper coloring impossible

        # Sets automatically discard duplicate edges.
        adjacency[left].add(right)
        adjacency[right].add(left)

    # More than n distinct colors are unnecessary.
    color_count = min(colors, len(vertices))
    order = sorted(vertices, key=lambda vertex: (-len(adjacency[vertex]), vertex))
    assignment: dict[int, int] = {}

    def is_safe(vertex: int, color: int) -> bool:
        return all(
            neighbor not in assignment or assignment[neighbor] != color
            for neighbor in adjacency[vertex]
        )

    def backtrack(position: int) -> bool:
        # Base case: every vertex has been colored.
        if position == len(order):
            return True

        vertex = order[position]

        for color in range(color_count):
            if not is_safe(vertex, color):
                continue  # Prune the conflicting branch safely.

            # Choose: assign a valid color.
            assignment[vertex] = color

            # Explore: color the remaining vertices.
            if backtrack(position + 1):
                return True

            # Unchoose: restore the previous state.
            del assignment[vertex]

        return False

    if backtrack(0):
        return assignment.copy()

    return None


edges = [(0, 1), (1, 2), (2, 3)]
result = solve_graph_coloring([0, 1, 2, 3], edges, 2)
print(result)
# {1: 0, 2: 1, 0: 1, 3: 0}

Edge Cases

  • Empty graph: returns an empty dictionary when colors > 0.

  • One vertex: assigns color 0.

  • Duplicate edges: collapsed by adjacency sets and do not affect the result.

  • Negative vertex identifiers: supported because they are dictionary keys.

  • Disconnected graphs: handled naturally; isolated vertices receive color 0.

  • Cycles: handled by the same neighbor-conflict checks.

  • Self-loop: returns None, since no proper coloring exists.

  • Already sorted input: input order does not matter because vertices are reordered by degree.

  • Invalid colors or vertices: raises ValueError; duplicate vertex identifiers are also rejected.

Common Pitfalls

  • Forgetting the base case causes recursion to continue beyond the last vertex.

  • Not undoing an assignment leaves stale colors in the state and produces incorrect branches.

  • Mutating the input can surprise callers; this implementation builds a separate adjacency structure.

  • Ignoring self-loops leads to an impossible coloring being reported.

  • Recursion depth: the recursive depth is O(n). For graphs with roughly 1,000 or more vertices, use an explicit stack or raise Python’s recursion limit.

  • Minimum coloring versus feasibility: this function tests whether k colors suffice. Finding the graph’s chromatic number generally requires testing increasing values of k, which is substantially more expensive because graph coloring is NP-hard.

24

How to solve the Knight's Tour problem with backtracking

A Knight’s Tour visits every square of a chessboard exactly once using legal knight moves. For an open tour, backtracking follows the choose / explore / un-choose pattern: mark the current square, try each legal next square, and undo the choice when that branch cannot produce a complete tour.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • State: current_path contains the squares in order, used contains the visited squares, and the search starts at (start_row, start_col).

  • Base case: len(current_path) == rows * cols; every square has then been visited.

  • Choose: add the current square to used and current_path.

  • Explore: try each of the eight knight moves and recursively visit legal, unused destinations.

  • Un-choose: remove the current square from both structures when its branch fails.

  • Result: when the base case is reached, save a copy of current_path.

Pruning and Heuristic

A candidate is pruned immediately when it is outside the board or already in used. This is safe because a knight cannot leave the board or revisit a square in an open tour. A branch with no remaining legal candidate also fails without exploring further.

Warnsdorff’s rule can reduce the practical search size by trying the destination with the fewest available onward moves first. It changes only the exploration order, however, and does not improve the exponential worst-case bound.

Complexity

Let N = rows * cols.

  • Best case: O(N) when the first explored branch completes a tour without backtracking.

  • Average case: data-dependent and potentially exponential; O(8^N) remains a safe general upper bound.

  • Worst case: O(8^N), because the search has depth at most N and at most eight choices per level. The search space is exponential.

  • Space: O(N) auxiliary space for current_path, used, the copied result, and the O(N) recursion stack. The scalar input is not counted; the returned board occupies O(N) space.

Walkthrough

For a 3x3 board using the move order in the code:

  1. Start at (0, 0) with move number 0.

  2. Choose (1, 2) for move 1.

  3. Choose (2, 0) for move 2.

  4. Choose (0, 1) for move 3.

  5. Choose (2, 2) for move 4.

  6. Choose (1, 0) for move 5.

  7. Choose (0, 2) for move 6.

  8. From (0, 2), choose (2, 1). That square’s only destinations are already used, so the branch is undone and backtracking continues.

Code Example

def knight_tour(
    rows: int,
    cols: int,
    start_row: int = 0,
    start_col: int = 0,
) -> list[list[int]]:
    """Return an open knight's tour, or an empty list if no tour exists."""
    if rows <= 0 or cols <= 0:
        raise ValueError("rows and cols must be positive")
    if not (0 <= start_row < rows and 0 <= start_col < cols):
        raise ValueError("start coordinates are outside the board")

    cell_count = rows * cols
    current_path: list[tuple[int, int]] = []
    used: set[tuple[int, int]] = set()
    tour_results: list[list[tuple[int, int]]] = []

    moves: tuple[tuple[int, int], ...] = (
        (-2, -1), (-2, 1), (-1, -2), (-1, 2),
        (1, -2), (1, 2), (2, -1), (2, 1),
    )

    def is_valid(row: int, col: int) -> bool:
        return (
            0 <= row < rows
            and 0 <= col < cols
            and (row, col) not in used
        )

    def backtrack(row: int, col: int) -> bool:
        # Choose: mark the current square and extend the path.
        used.add((row, col))
        current_path.append((row, col))
        found = False

        # Base case: every square has been visited.
        if len(current_path) == cell_count:
            tour_results.append(current_path.copy())
            found = True
        else:
            # Explore: try every legal knight move.
            for row_delta, col_delta in moves:
                next_row = row + row_delta
                next_col = col + col_delta
                if is_valid(next_row, next_col):
                    if backtrack(next_row, next_col):
                        found = True
                        break

        # Un-choose: restore the state before returning.
        used.remove((row, col))
        current_path.pop()
        return found

    if not backtrack(start_row, start_col):
        return []

    board = [[-1] * cols for _ in range(rows)]
    for move_number, (row, col) in enumerate(tour_results[0]):
        board[row][col] = move_number
    return board


tour = knight_tour(5, 5, 0, 0)
for row in tour:
    print(row)
# Expected output:
# [0, 17, 4, 9, 2]
# [5, 10, 1, 18, 13]
# [16, 21, 12, 3, 8]
# [11, 6, 23, 14, 19]
# [22, 15, 20, 7, 24]

Common Pitfalls

  • Empty or invalid input: non-positive dimensions and out-of-range starts raise ValueError; a 1 x 1 board returns [[0]].

  • No solution: return an empty list when every branch fails. A 3x3 board has an isolated center and cannot have a complete tour, and a 4x4 board has no knight’s tour at all.

  • Duplicates and cycles: the used set prevents repeated squares; a closed tour must separately verify that the final square can legally return to the start.

  • Off-by-one errors: success occurs when the path contains rows * cols squares, not when a move index equals that value.

  • Recursion depth: a board with roughly 1,000 or more squares can exceed Python’s default recursion limit. Use an explicit stack or raise the limit; Warnsdorff’s rule does not reduce stack depth.

  • Irrelevant input properties: negative values, sorted input, and duplicate numeric values do not apply to this grid-search problem.

25

How does backtracking solve cryptarithmetic puzzles?

Backtracking solves cryptarithmetic puzzles by assigning digits to letters incrementally, exploring each possible assignment, and undoing choices that create a contradiction. Column-by-column arithmetic prunes invalid branches early by checking digit uniqueness, leading-zero rules, column sums, and carries.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

A cryptarithmetic puzzle represents an equation such as:

SEND + MORE = MONEY

Each letter represents one digit, the same letter always represents the same digit, different letters use different digits, and a leading letter cannot represent zero.

The algorithm works from the rightmost column to the leftmost:

  • Choose: Try an unused digit for an unassigned letter.

  • Explore: Recursively process the current column and then move to the next column.

  • Unchoose: If the column fails, remove the assignment and try another digit.

The main state consists of:

  • current_path: the letters and digits assigned so far.

  • used_digits: the digits already assigned.

  • start_index: the next column to process, counted from the units column.

  • carry: the carry entering the current column.

The base case occurs when every column has been processed and the final carry is zero.

Pruning and Column Equations

A branch is discarded immediately when:

  • A digit is already used by another letter.

  • A leading letter is assigned zero.

  • The result digit does not match the column sum.

  • The carry cannot be represented by the remaining result columns.

For SEND + MORE = MONEY, the column equations are:

Column Equation
Units D + E = Y + 10 × carry₁
Tens N + R + carry₁ = E + 10 × carry₂
Hundreds E + O + carry₂ = N + 10 × carry₃
Thousands S + M + carry₃ = O + 10 × carry₄
Ten-thousands carry₄ = M

A complete solution is:

9567 + 1085 = 10652

Code Example

def solve_cryptarithmetic(
    addends: list[str], result: str
) -> dict[str, int] | None:
    """Solve a cryptarithmetic addition and return one digit mapping."""
    words = [*addends, result]

    if not words or any(not word for word in words):
        return None
    if any(not all("A" <= char <= "Z" for char in word) for word in words):
        return None

    letters = set("".join(words))
    if len(letters) > 10:
        return None

    max_addend_length = max(len(word) for word in addends)
    if len(result) < max_addend_length:
        return None

    leading_letters = {word[0] for word in words}
    reversed_result = result[::-1]
    column_count = max(len(word) for word in words)

    columns: list[list[str]] = [[] for _ in range(column_count)]
    for word in addends:
        for offset, letter in enumerate(reversed(word)):
            columns[offset].append(letter)

    current_path: list[tuple[str, int]] = []
    used_digits: set[int] = set()
    solutions: list[dict[str, int]] = []

    def get_assignment(letter: str) -> int | None:
        for assigned_letter, digit in current_path:
            if assigned_letter == letter:
                return digit
        return None

    def can_use(letter: str, digit: int) -> bool:
        return not (
            digit in used_digits
            or (digit == 0 and letter in leading_letters)
        )

    def assign_letter(letter: str, digit: int) -> None:
        current_path.append((letter, digit))
        used_digits.add(digit)

    def unassign_letter(letter: str, digit: int) -> None:
        current_path.pop()
        used_digits.remove(digit)

    def search(start_index: int, carry: int) -> bool:
        # Base case: all columns processed and no remaining carry.
        if start_index == column_count:
            if carry == 0:
                solutions.append(dict(current_path))
                return True
            return False

        return fill_column(start_index, carry, 0)

    def fill_column(
        start_index: int, carry: int, letter_index: int
    ) -> bool:
        column_letters = list(dict.fromkeys(columns[start_index]))

        if letter_index < len(column_letters):
            letter = column_letters[letter_index]
            existing_digit = get_assignment(letter)

            if existing_digit is not None:
                return fill_column(start_index, carry, letter_index + 1)

            for digit in range(10):
                if not can_use(letter, digit):
                    continue

                # CHOOSE: assign a candidate digit.
                assign_letter(letter, digit)

                # EXPLORE: continue with this assignment.
                if fill_column(start_index, carry, letter_index + 1):
                    return True

                # UNCHOOSE: undo the failed assignment.
                unassign_letter(letter, digit)

            return False

        total = carry + sum(
            get_assignment(letter) or 0 for letter in column_letters
        )
        expected_digit = total % 10
        next_carry = total // 10
        result_letter = reversed_result[start_index]

        existing_digit = get_assignment(result_letter)
        if existing_digit is not None:
            if existing_digit != expected_digit:
                return False
            return search(start_index + 1, next_carry)

        if not can_use(result_letter, expected_digit):
            return False

        # CHOOSE: assign the result digit required by this column.
        assign_letter(result_letter, expected_digit)

        # EXPLORE: process the next column.
        if search(start_index + 1, next_carry):
            return True

        # UNCHOOSE: remove the result assignment.
        unassign_letter(result_letter, expected_digit)
        return False

    search(0, 0)
    return solutions[0] if solutions else None


if __name__ == "__main__":
    solution = solve_cryptarithmetic(["SEND", "MORE"], "MONEY")
    if solution is None:
        print(None)
    else:
        print({letter: solution[letter] for letter in sorted(solution)})

    # Expected output:
    # {'D': 7, 'E': 5, 'M': 1, 'N': 6, 'O': 0, 'R': 8, 'S': 9, 'Y': 2}

Complexity

Let:

  • L be the number of distinct letters.

  • C be the number of columns.

  • P(10, L) = 10! / (10 - L)! be the number of possible injective digit assignments.

Case Time Space
Best O(L + C) if the first branch is valid O(L + C)
Average Puzzle-dependent; no single average bound is meaningful O(L + C)
Worst O(C × L × P(10, L)) O(L + C)

The time complexity is factorial, not merely exponential, because the search space consists of permutations of digits among letters. The space complexity includes current_path, used_digits, the recursion stack, and the stored solution, but excludes the input words themselves.

Common Pitfalls

  • Leading zeros: The first letter of every addend and the result must be nonzero.

  • Duplicate digits: Two different letters cannot share a digit.

  • Incorrect carry handling: The carry belongs to the next column on the left.

  • Mutable state: Always undo assignments when a branch fails, and copy the path when storing a solution.

  • Empty or invalid input: The implementation rejects empty words, non-uppercase letters, more than ten distinct letters, and an undersized result.

  • Interview follow-up: Interviewers commonly ask about improving pruning, handling multiple solutions, supporting subtraction, and explaining why column-wise processing is faster than checking complete assignments.

26

How do you solve the Hamiltonian path problem with backtracking?

A Hamiltonian path visits every vertex in a graph exactly once, although it does not need to return to its starting vertex. Backtracking constructs the path incrementally, explores only valid extensions, and removes vertices when a branch cannot lead to a complete solution.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The algorithm maintains three pieces of state:

  • Current path: the vertices selected so far.

  • Used set: the vertices already in the path.

  • Stack frame: the current vertex and the index of its next neighbor to examine.

The explicit stack replaces recursion, so the implementation is not limited by Python’s default recursion depth.

For each possible starting vertex:

  1. Choose the starting vertex and mark it used.

  2. Explore each adjacent vertex that is not already used.

  3. Choose the neighbor by adding it to the path and used set.

  4. Continue recursively or iteratively.

  5. If the current vertex has no remaining valid neighbor, unchoose it and backtrack.

  6. A complete path is found when the path length equals the number of vertices.

Pruning is safe because a Hamiltonian path cannot contain a repeated vertex. Therefore, any neighbor already in the used set can be skipped immediately.

The implementation treats the graph as a directed graph represented by an adjacency list. For an undirected graph, each edge must appear in both endpoints’ adjacency lists.

Complexity

Let n be the number of vertices and m the number of listed adjacency entries.

  • Best case: O(n + m) when a complete path is found without backtracking.

  • Average case: Graph-dependent; there is no single meaningful average bound because the number of explored prefixes varies by graph and neighbor order.

  • Worst case: O(n · n!) time. The search can examine up to O(n!) partial permutations, and each state may scan up to n neighbors.

  • Space: O(n + m) auxiliary space, including the copied normalized adjacency lists, explicit stack, current path, and used set. The search state itself uses O(n) space. The input graph is not counted.

The search space is factorial rather than polynomial. Hamiltonian path is NP-complete for general graphs, so no known polynomial-time exact algorithm exists for arbitrary graphs.

Approach Time Extra space When to use
Check every permutation O(n · n!) O(n) Simple baseline or small graphs
Backtracking with pruning O(n · n!) worst case, often less O(n + m) General exact solution with early pruning

Code Example

def hamiltonian_path(
    adjacency_list: list[list[int]],
) -> list[int] | None:
    """Return one Hamiltonian path, or None if no Hamiltonian path exists."""
    vertex_count = len(adjacency_list)

    # Convention: the empty graph has the empty path.
    if vertex_count == 0:
        return []

    neighbors: list[list[int]] = []

    for vertex, row in enumerate(adjacency_list):
        for neighbor in row:
            if neighbor < 0 or neighbor >= vertex_count:
                raise ValueError(
                    f"Neighbor {neighbor} is not a valid vertex index."
                )

        # Remove duplicate edges without changing their input order.
        neighbors.append(list(dict.fromkeys(row)))

    for start_index in range(vertex_count):
        current_path: list[int] = [start_index]
        used: set[int] = {start_index}

        # Each frame is (current vertex, next neighbor index).
        stack: list[tuple[int, int]] = [(start_index, 0)]

        while stack:
            current_vertex, next_neighbor_index = stack[-1]

            # BASE CASE: every vertex has been visited exactly once.
            if len(current_path) == vertex_count:
                return current_path.copy()

            if next_neighbor_index == len(neighbors[current_vertex]):
                # UNCHOOSE: this branch is exhausted, so backtrack.
                stack.pop()
                removed_vertex = current_path.pop()
                used.remove(removed_vertex)
                continue

            # Advance the frame before descending into a neighbor.
            stack[-1] = (
                current_vertex,
                next_neighbor_index + 1,
            )
            candidate = neighbors[current_vertex][next_neighbor_index]

            # EXPLORE: already-used vertices cannot extend a Hamiltonian path.
            if candidate in used:
                continue

            # CHOOSE: extend the current path with an unused neighbor.
            current_path.append(candidate)
            used.add(candidate)

            # EXPLORE: the extended path is processed on the next iteration.
            stack.append((candidate, 0))

    return None


if __name__ == "__main__":
    graph = [
        [1, 2],
        [0, 2],
        [0, 1, 3],
        [2],
    ]

    result = hamiltonian_path(graph)
    print(result)  # Output: [0, 1, 2, 3]

Common Pitfalls

  • Confusing a path with a cycle: A Hamiltonian path does not require an edge from the final vertex back to the first.

  • Failing to handle disconnected graphs: If no spanning path exists, the function returns None.

  • Mutating the input: The implementation copies and normalizes adjacency lists instead of modifying the caller’s graph.

  • Ignoring duplicate edges: Duplicate neighbor entries are harmless and are removed before searching.

  • Incorrect base case: The base case is based on visiting all n vertices, not on returning to the start.

  • Using recursion for very large graphs: This implementation uses an explicit stack, avoiding Python’s recursion-depth limit.

Interview Tips

Explain that the algorithm follows choose, explore, unchoose:

  • Choose: add an unused neighbor.

  • Explore: continue searching from that neighbor.

  • Unchoose: remove the vertex when its branch is exhausted.

Common follow-up questions ask about improving pruning using degree checks or connectivity analysis, handling directed versus undirected graphs, and why the worst-case complexity remains factorial.

27

How do you solve the Word Break problem with backtracking?

Backtracking solves Word Break by trying each dictionary word that matches the current suffix, recursively checking the remaining text, and undoing the choice when that route fails. A trie and memoized failed suffixes prevent the exponential search from repeatedly solving the same suffix.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Approach

At each recursive call, the state consists of:

  • start: index of the first character not yet segmented.

  • path: words selected for the current segmentation.

  • failed_starts: suffixes already proven impossible to segment.

A used set is unnecessary because dictionary words may be reused. The recursive operation is:

  1. Choose a dictionary word matching the text at start.

  2. Explore the remaining suffix.

  3. Un-choose the word if the exploration fails.

Approach Time Auxiliary Space When to Use
Unmemoized backtracking O(n · 2^n) worst O(n + k) Small inputs or teaching
Memoized backtracking with trie O(n² + W) O(n + W) Practical backtracking implementation
Dynamic programming with trie O(n² + W) O(n + W) Iterative production solution

Here, n is the text length, k is the number of dictionary words, and W is the total number of characters in the dictionary.

State and Pruning

The base case occurs when start == len(text): every character has been segmented successfully.

Pruning is safe because:

  • Trie-prefix pruning: traversal stops when the next character has no matching trie edge. No dictionary word can match that prefix.

  • Failed-suffix memoization: if segmentation is impossible from one start, it is impossible from every path reaching the same suffix. Future choices depend only on start, not on path.

  • Empty-word removal: empty dictionary entries are ignored because they would not advance the search position.

The underlying search space contains up to 2^(n-1) possible ways to place cuts between characters, which is exponential. Memoization collapses repeated suffix exploration to at most n + 1 distinct starting positions.

Example Walkthrough

For text = "leetcode" and words ["leet", "code"]:

Step start path Action
1 0 [] Choose "leet"
2 4 ["leet"] Choose "code"
3 8 ["leet", "code"] Reach the base case and return True

If "code" were absent, the algorithm would un-choose it, return to start = 4, and try other available words.

Complexity

For the implemented memoized backtracking solution:

  • Best time: O(n + W), when the text is segmented without exploring many alternatives.

  • Average time: O(n² + W), since each of at most n + 1 suffix states may scan up to n trie characters.

  • Worst time: O(n² + W), because failed suffixes are memoized and each suffix is processed at most once.

  • Auxiliary space: O(n + W), including the trie, recursion stack, current path, and failed-suffix set. The original text and dictionary input are not counted.

The recursive depth can reach O(n). For strings approaching Python’s default recursion limit of roughly 1,000, use an explicit stack or carefully raise the limit.

Code Example

from __future__ import annotations

from collections.abc import Iterable
from dataclasses import dataclass, field


@dataclass(slots=True)
class _TrieNode:
    children: dict[str, _TrieNode] = field(default_factory=dict)
    is_word: bool = False


def word_break(text: str, words: Iterable[str]) -> bool:
    """Return whether text can be segmented into dictionary words."""
    root = _TrieNode()

    for word in words:
        if not word or len(word) > len(text):
            continue

        node = root
        for character in word:
            child = node.children.get(character)
            if child is None:
                child = _TrieNode()
                node.children[character] = child
            node = child
        node.is_word = True

    path: list[str] = []
    failed_starts: set[int] = set()

    def backtrack(start: int) -> bool:
        # Base case: every character has been consumed.
        if start == len(text):
            return True

        if start in failed_starts:
            return False

        node = root

        for end in range(start, len(text)):
            child = node.children.get(text[end])
            if child is None:
                # No dictionary word has this prefix.
                break
            node = child

            if not node.is_word:
                continue

            segment = text[start : end + 1]

            # Choose: add a matching word to the current path.
            path.append(segment)

            # Explore: recursively segment the remaining suffix.
            if backtrack(end + 1):
                return True

            # Un-choose: remove the word after an unsuccessful branch.
            path.pop()

        failed_starts.add(start)
        return False

    return backtrack(0)


print(word_break("leetcode", ["leet", "code"]))  # True

Common Pitfalls

  • Returning False for empty text; the standard convention is that an empty string is successfully segmented.

  • Forgetting that words may repeat and therefore must not be tracked with a used set.

  • Treating empty dictionary words as valid segments.

  • Missing the start == len(text) base case or advancing by an empty string.

  • Ignoring Python’s recursion-depth limit for long inputs.

  • Mutating the input collection; this implementation leaves both inputs unchanged.

  • Integer overflow does not occur in Python, although equivalent implementations in fixed-width languages need sufficiently large types.

  • Negative numbers, sorted input, disconnected graphs, and cycles are not applicable to this problem.

28

How can backtracking produce every palindrome partition of a string?

Palindrome partitioning uses backtracking to choose a palindromic prefix, recursively partition the remaining suffix, and then undo each choice before exploring alternatives. The algorithm returns every possible partition without modifying the input string.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

The backtracking state contains:

  • current_path: the palindrome substrings selected for the current partition.

  • start_index: the next character to partition.

  • Used set: not required because each character position is consumed exactly once.

For each possible endpoint, the algorithm checks whether text[start_index:end + 1] is a palindrome:

  1. Choose: append the palindromic substring to current_path.

  2. Explore: recursively process the suffix beginning at end + 1.

  3. Un-choose: remove the substring after returning from recursion.

The base case occurs when start_index == len(text). At that point, every character has been assigned to a palindrome, so a copy of current_path is added to the results.

Pruning

Non-palindromic candidates are rejected immediately. This pruning is safe because every element of a valid palindrome partition must itself be a palindrome; extending a non-palindromic prefix could never produce a valid partition containing that prefix.

Complexity

For a string of length n:

  • Best case: Θ(n²). The algorithm still examines O(n²) candidate substrings, although only the singleton-character partition survives.

  • Average case: input-dependent; there is no standard average without defining a probability distribution over strings.

  • Worst case: O(n * 2^n), which is exponential. A string containing one repeated character has up to 2^(n-1) partitions, and each palindrome check can take O(n) time.

  • Auxiliary space: O(n), including the recursion stack and current_path; the input string is not counted.

  • Output space: O(n * 2^n) in the worst case because all partitions are retained.

Code Example

def partition_palindromes(text: str) -> list[list[str]]:
    """Return every partition of text whose substrings are palindromes."""
    results: list[list[str]] = []
    current_path: list[str] = []

    def is_palindrome(left: int, right: int) -> bool:
        while left < right:
            if text[left] != text[right]:
                return False
            left += 1
            right -= 1
        return True

    def backtrack(start_index: int) -> None:
        # Base case: every character has been assigned to a palindrome.
        if start_index == len(text):
            results.append(current_path.copy())
            return

        for end in range(start_index, len(text)):
            # Prune candidates that cannot appear in a valid partition.
            if not is_palindrome(start_index, end):
                continue

            # Choose the palindromic substring.
            current_path.append(text[start_index:end + 1])

            # Explore partitions of the remaining suffix.
            backtrack(end + 1)

            # Un-choose the substring and try another endpoint.
            current_path.pop()

    backtrack(0)
    return results


print(partition_palindromes("aab"))
# Expected: [['a', 'a', 'b'], ['aa', 'b']]

Walkthrough

For "aab":

State Action Current path
Start at index 0 Choose "a" ["a"]
Start at index 1 Choose "a" ["a", "a"]
Start at index 2 Choose "b" and reach the base case ["a", "a", "b"]
Backtrack to index 1 Reject "ab" because it is not a palindrome ["a"]
Backtrack to index 0 Choose "aa" ["aa"]
Start at index 2 Choose "b" and reach the base case ["aa", "b"]

Common Pitfalls

  • Appending the path itself: use current_path.copy() or current_path[:]; otherwise every result may reference the same mutable list.

  • Forgetting to un-choose: failing to call current_path.pop() contaminates later branches.

  • Off-by-one errors: the recursive call must start at end + 1.

  • Empty input: this implementation returns [[]], representing the partition containing no substrings.

  • One element or duplicates: a single character returns [["a"]]; repeated characters may create multiple valid cut patterns.

  • Recursion depth: the stack can reach O(n). Strings longer than Python’s default recursion limit may require an explicit stack or a carefully increased limit.

  • Numeric ordering, sorted input, disconnected graphs, and cycles are not applicable to palindrome partitioning.

Interviewers commonly ask about the base case, pruning, output copying, exponential complexity, and how memoization could avoid recomputing palindrome checks or suffix results.

29

How do you solve combination sum using backtracking?

Backtracking solves combination sum by choosing a candidate, recursively exploring the remaining sum, and then undoing the choice. The start_index preserves nondecreasing combinations while allowing a candidate to be reused.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Approach

The state consists of:

  • current_path: the combination currently being constructed.

  • start_index: the first candidate that may be selected next.

  • remaining: the amount still needed to reach the target.

The recursive base case is remaining == 0. At that point, a copy of current_path is added to the results.

The same candidate index is passed recursively, so values may be reused. However, start_index prevents generating the same combination in a different order.

Example Walkthrough

For candidates = [2, 3, 6, 7] and target = 7:

  1. Choose 2: current_path = [2], remaining is 5.

  2. Choose 2 again: current_path = [2, 2], remaining is 3.

  3. Choose 3: current_path = [2, 2, 3], remaining is 0.

  4. Save [2, 2, 3], then undo the choices.

  5. Choose 7 directly and save [7].

The result is [[2, 2, 3], [7]].

Pruning

Because candidates are sorted, exploration can stop when:

  • candidate > remaining: the candidate and every later candidate are too large.

  • remaining == 0: a complete combination has been found, so no further exploration is needed.

These cuts are safe because all candidates are positive and the recursion only constructs nondecreasing combinations.

Complexity

Let:

  • m be the number of input candidates.

  • k be the number of distinct candidate values.

  • r = floor(target / minimum_candidate) be the maximum combination length.

  • S be the number of returned combinations.

The search can visit combinations with repetition, so its general size is bounded by O(C(k + r, r)). This is a combinatorial, potentially exponential search space.

  • Best time: O(m log m) for deduplication and sorting, with no recursive exploration when the smallest candidate exceeds the target.

  • Average time: depends on how often candidates fit the remaining sum; there is no single meaningful average without defining a candidate distribution.

  • Worst time: O(m log m + C(k + r, r) + r × S), including the search and copying returned combinations. An O(m × 2^m) bound applies only to the variant where each candidate can be used at most once.

  • Auxiliary space: O(k + r), including the sorted candidate copy, current path, and recursion stack. The input itself is excluded.

  • Output space: O(r × S).

  • Total space including input and output: O(m + r + r × S).

Code Example

from collections.abc import Sequence


def combination_sum(
    candidates: Sequence[int], target: int
) -> list[list[int]]:
    """Return all nondecreasing combinations that sum to target."""
    if any(candidate <= 0 for candidate in candidates):
        raise ValueError("Candidates must be positive integers.")

    if target <= 0 or not candidates:
        return []

    values = sorted(set(candidates))
    if values[0] > target:
        return []

    results: list[list[int]] = []
    current_path: list[int] = []

    def backtrack(start_index: int, remaining: int) -> None:
        # Base case: a complete combination was found.
        if remaining == 0:
            results.append(current_path.copy())
            return

        for index in range(start_index, len(values)):
            candidate = values[index]

            # Pruning: later candidates are also too large.
            if candidate > remaining:
                break

            # Choose the candidate.
            current_path.append(candidate)

            # Explore; keep the same index to allow candidate reuse.
            backtrack(index, remaining - candidate)

            # Un-choose the candidate.
            current_path.pop()

    backtrack(0, target)
    return results


print(combination_sum([2, 3, 6, 7], 7))
# Expected output: [[2, 2, 3], [7]]

Common Pitfalls

  • Appending the mutable path: use current_path.copy(), not current_path, or later modifications will change saved results.

  • Losing the reuse rule: recurse with index, not index + 1, when the same candidate may be selected again.

  • Generating duplicate combinations: recurse only from start_index and remove duplicate input values.

  • Invalid candidates: zero candidates cause infinite recursion, while negative candidates invalidate the remaining-sum pruning. The implementation rejects both.

  • Edge cases: empty input and a nonpositive target return []; one candidate is handled and may be reused; duplicate values are removed; an already sorted input behaves identically because the implementation creates a sorted, deduplicated copy.

  • Recursion depth: the recursive implementation needs a raised recursion limit or an explicit stack when target // minimum_candidate can exceed Python’s roughly 1,000-frame default limit.

  • Common follow-up: interviewers may ask how to return only the number of combinations, prevent candidate reuse, or handle negative values with a different state and pruning strategy.

30

How do you implement backtracking to restore valid IPv4 addresses?

Backtracking restores every valid IPv4 address by repeatedly choosing an octet, exploring that choice, and then undoing it. Pruning rejects invalid segments and impossible remaining lengths early.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

Each valid IPv4 address contains exactly four groups separated by dots. Each group must:

  • Contain only digits.

  • Contain between one and three digits.

  • Represent a value from 0 through 255.

  • Have no leading zero unless the group is exactly "0".

The algorithm follows the choose/explore/un-choose pattern:

  1. Choose: Add a valid candidate octet to the current path.

  2. Explore: Recursively process the remaining substring.

  3. Un-choose: Remove the octet so another candidate can be tried.

The state consists of:

  • current_path: the octets selected so far.

  • start_index: where the next octet begins.

  • groups_used: how many of the four required octets have been selected.

  • Used set: Not needed because selected groups are contiguous, non-overlapping slices of the input.

Pruning

The search stops early when:

  • A candidate starts with zero and contains multiple digits.

  • A candidate represents a value greater than 255.

  • Too few characters remain to form the remaining groups.

  • Too many characters remain, since each remaining group can contain at most three digits.

These checks are safe because adding more groups cannot repair an already invalid octet or change the number of characters available for the remaining groups.

Example Walkthrough

For "25525511135", one successful path is:

Step Current path Start index Chosen group
1 [] 0 "255"
2 ["255"] 3 "255"
3 ["255", "255"] 6 "11"
4 ["255", "255", "11"] 8 "135"

The result is "255.255.11.135". Backtracking then tries "111" instead of "11", producing "255.255.111.35".

Code Example

def restore_ip_addresses(number_string: str) -> list[str]:
    """Return every valid IPv4 address that can be formed from number_string."""
    if not number_string:
        return []

    # Four groups of one to three digits require 4 through 12 characters.
    if not 4 <= len(number_string) <= 12:
        return []

    # Reject signs, whitespace, decimal points, and non-ASCII digits.
    if any(char < "0" or char > "9" for char in number_string):
        return []

    valid_paths: list[list[str]] = []
    current_path: list[str] = []

    def backtrack(start_index: int, groups_used: int) -> None:
        remaining_groups = 4 - groups_used
        remaining_characters = len(number_string) - start_index

        # Base case: exactly four groups must consume the entire string.
        if remaining_groups == 0:
            if start_index == len(number_string):
                valid_paths.append(current_path[:])
            return

        # Prune impossible remaining lengths.
        if remaining_characters < remaining_groups:
            return
        if remaining_characters > 3 * remaining_groups:
            return

        for segment_length in range(1, min(3, remaining_characters) + 1):
            segment = number_string[start_index:start_index + segment_length]

            # Leading zeros are allowed only for the group "0".
            if segment_length > 1 and segment[0] == "0":
                continue

            if int(segment) > 255:
                continue

            # Choose: add the next octet to the current path.
            current_path.append(segment)

            # Explore: process the remaining substring.
            backtrack(start_index + segment_length, groups_used + 1)

            # Un-choose: restore the path before trying another candidate.
            current_path.pop()

    backtrack(start_index=0, groups_used=0)
    return [".".join(path) for path in valid_paths]


print(restore_ip_addresses("25525511135"))
# ['255.255.11.135', '255.255.111.35']

Complexity

  • Best, average, and worst-case time: O(n³) in the general partition model. There are three group boundaries, each with at most O(n) possible positions, so the search space is bounded by C(n-1, 3). For actual IPv4 candidates, n is at most 12, making the search practically bounded and constant-sized.

  • Search-space classification: Unlike generic subset backtracking, this problem is not exponential, because exactly four groups are required and each group has at most three possible lengths.

  • Auxiliary space: O(1), including the recursion stack and current_path, because there are at most four decisions. The input string is not counted.

  • Output space: O(R), where R is the number of valid addresses returned.

Common Pitfalls

  • Accepting leading zeros such as "01".

  • Allowing octets greater than 255.

  • Forgetting to restore the current path after recursion.

  • Storing the mutable path rather than copying it into the results.

  • Returning early after finding the first address; the task requires all addresses.

  • Empty or one-character strings are rejected, while "0000" produces "0.0.0.0".

  • Repeated digits can create multiple valid partitions and should not be deduplicated.

  • Negative signs are invalid, and character order is preserved, so already-sorted input receives no special treatment.

31

How do you find all directed source-to-target paths with backtracking?

Use a depth-first backtracking search that maintains the current path, explores each outgoing neighbor, and removes that neighbor when returning so it can participate in other paths. A visited set tracks only the current path, preventing cycles without incorrectly blocking vertices that belong to multiple valid paths.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Backtracking Approach

The search maintains three pieces of state:

  • current_path: the vertices selected from the source to the current node.

  • used: the vertices in the current path, used to prevent revisiting a vertex and creating cycles.

  • results: completed source-to-target paths.

At each node:

  1. Choose the node by adding it to current_path and used.

  2. If the node is the target, save a copy of the path.

  3. Otherwise, explore every outgoing neighbor that is not in used.

  4. Un-choose the node by removing it from both current_path and used.

Because the graph is directed, only neighbors listed under the current node are explored.

Example Walkthrough

For this graph:

A -> B, C
B -> D
C -> D
D -> []

The search proceeds as follows:

  1. Choose A: current_path = [A].

  2. Explore B: current_path = [A, B].

  3. Explore D: current_path = [A, B, D].

  4. Save [A, B, D], then backtrack.

  5. Explore C: current_path = [A, C].

  6. Explore D: current_path = [A, C, D].

  7. Save [A, C, D], then backtrack.

Duplicate outgoing entries are ignored so the same vertex sequence is not returned twice.

Complexity

Let n be the number of vertices, m the number of edges, P the number of simple path prefixes explored, and R the number of returned paths.

  • Best case: O(1) when the source is already the target.

  • Average case: O(nP), depending entirely on the graph structure; there is no meaningful universal average for arbitrary directed graphs.

  • Worst case: O(n · n!). The search space is exponential in the broad sense and can be factorial when cycles and a dense directed graph permit many simple paths.

  • Auxiliary space: O(n), including the recursion stack, current_path, and used, excluding the input graph and returned results.

  • Returned-result space: O(nR).

  • Input space, if counted: O(n + m) for the adjacency structure.

No amortized bound applies; the runtime depends on the number of explored path prefixes and output paths.

Code Example

from collections.abc import Mapping, Sequence


def all_paths_from_source_to_target(
    adjacency: Mapping[str, Sequence[str]],
    source: str,
    target: str,
) -> list[list[str]]:
    """Return every simple directed path from source to target."""
    results: list[list[str]] = []
    current_path: list[str] = []
    used: set[str] = set()

    def backtrack(node: str) -> None:
        # Choose: add the current node to the path and used set.
        current_path.append(node)
        used.add(node)

        # Base case: a complete source-to-target path has been found.
        if node == target:
            results.append(current_path[:])
        else:
            # dict.fromkeys removes duplicate neighbors while preserving order.
            for neighbor in dict.fromkeys(adjacency.get(node, ())):
                if neighbor not in used:
                    # Explore the next valid path.
                    backtrack(neighbor)

        # Un-choose: restore the state before exploring another branch.
        current_path.pop()
        used.remove(node)

    if source not in adjacency:
        return results

    backtrack(source)
    return results


graph = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": ["D"],
    "D": [],
}

print(all_paths_from_source_to_target(graph, "A", "D"))
# Expected output: [['A', 'B', 'D'], ['A', 'C', 'D']]

Common Pitfalls

  • Using a global visited set: This blocks vertices needed by later branches. The visited set must represent only the current path.

  • Saving the mutable path: Use current_path[:]. Saving current_path directly causes previously recorded results to change during backtracking.

  • Forgetting to remove the node during backtracking: The search then loses alternative branches.

  • Treating the graph as undirected: Do not traverse reverse edges unless they are explicitly present in the adjacency list.

  • Recursion depth: A recursive implementation can exceed Python’s default recursion limit for graphs with more than roughly 1,000 vertices on the path. Use an explicit stack or increase the limit carefully.

  • Target handling: The search stops when it reaches the target, so paths that continue beyond the target are not included.

32

How does backtracking work in AI game-playing algorithms?

Backtracking lets an AI explore a game tree by making a move, recursively evaluating the resulting position, and then undoing the move. In adversarial games, this recursive search is commonly combined with minimax and alpha-beta pruning to choose optimal moves efficiently.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How Backtracking Is Used in Games

A game-playing AI represents each position as a state. At each state, it:

  1. Chooses a legal move.

  2. Explores the resulting state recursively.

  3. Undoes the move to restore the parent state.

The search tree contains every sequence of moves that could be played. A terminal state is evaluated as a win, loss, or draw, while an intermediate state receives a value based on its descendants.

Backtracking also appears in constraint-based game tasks, such as generating legal chess sequences or solving Sudoku-like puzzles where choices are made, checked, and rejected when they violate a constraint.

Minimax and Pruning

In a two-player, perfect-information game, minimax assumes that both players play optimally:

  • The maximizing player chooses the highest-valued child.

  • The minimizing player chooses the lowest-valued child.

  • A win is positive, a loss is negative, and a draw is zero.

Alpha-beta pruning reduces the tree searched. Each branch carries bounds:

  • alpha: the best score the maximizing player can already guarantee.

  • beta: the best score the minimizing player can already guarantee.

  • If alpha >= beta, the remaining moves in that node cannot change the ancestor’s decision and are safely cut off.

Approach Time Auxiliary space When to use
Full minimax Θ(s × b^d) Θ(s + d) Small trees and teaching
Minimax with alpha-beta Best Θ(s × b^(d/2)), worst Θ(s × b^d) Θ(s + d) Deterministic, perfect-information games
Expectimax or MCTS Depends on simulations Depends on stored states Stochastic or imperfect-information games

Here, b is the maximum branching factor, d is the maximum game depth, and s is the state size. The unpruned search space is Θ(b^d), which is exponential in depth. Alpha-beta’s average runtime depends heavily on move ordering and therefore has no universal tighter bound. Space includes an O(d) recursion stack and path tracking plus an O(s) defensive state copy; the caller’s input is not counted.

Walkthrough of One Search Branch

For tic-tac-toe, one illustrative branch is:

Depth Path Position
0 [] Empty board
1 [0] X occupies cell 0
2 [0, 1] O occupies cell 1
3 [0, 1, 2] X occupies cell 2
4 [0, 1, 2, 3] O occupies cell 3
5 [0, 1, 2, 3, 4] X occupies cell 4
6 [0, 1, 2, 3, 4, 5] O occupies cell 5
7 [0, 1, 2, 3, 4, 5, 6] X occupies cell 6 and wins on the diagonal 2-4-6; the score is 1

The algorithm then un-changes the moves while returning to earlier states and explores other legal choices.

Code Example

from typing import Literal

Player = Literal["X", "O"]


def terminal_score(board: list[str]) -> int | None:
    lines = (
        (0, 1, 2), (3, 4, 5), (6, 7, 8),
        (0, 3, 6), (1, 4, 7), (2, 5, 8),
        (0, 4, 8), (2, 4, 6),
    )

    for first, second, third in lines:
        if board[first] == board[second] == board[third] != "":
            return 1 if board[first] == "X" else -1

    if all(cell != "" for cell in board):
        return 0

    return None


def best_move(board: list[str], player: Player) -> tuple[int, int | None]:
    """Return the minimax score and best move for a tic-tac-toe board."""
    if len(board) != 9 or any(cell not in ("", "X", "O") for cell in board):
        raise ValueError("board must contain exactly nine valid cells")

    working_board = board.copy()
    current_path: list[int] = []
    used_cells: set[int] = {
        index for index, cell in enumerate(working_board) if cell != ""
    }

    def search(
        board: list[str],
        maximizing: bool,
        alpha: int,
        beta: int,
        current_path: list[int],
        used_cells: set[int],
    ) -> tuple[int, int | None]:
        # Base case: terminal win, loss, or draw.
        score = terminal_score(board)
        if score is not None:
            return score, None

        current_player: Player = "X" if maximizing else "O"
        best_score = -10**9 if maximizing else 10**9
        best_index: int | None = None

        for index in range(len(board)):
            if index in used_cells:
                continue

            # Choose: place a move and update the current path.
            board[index] = current_player
            current_path.append(index)
            used_cells.add(index)

            # Explore: evaluate the child position.
            child_score, _ = search(
                board,
                not maximizing,
                alpha,
                beta,
                current_path,
                used_cells,
            )

            # Un-choose: restore the parent position.
            board[index] = ""
            current_path.pop()
            used_cells.remove(index)

            if maximizing:
                if child_score > best_score:
                    best_score, best_index = child_score, index
                alpha = max(alpha, best_score)
            else:
                if child_score < best_score:
                    best_score, best_index = child_score, index
                beta = min(beta, best_score)

            # Prune: this branch cannot change the ancestor's decision.
            if alpha >= beta:
                break

        return best_score, best_index

    return search(
        working_board,
        player == "X",
        -10**9,
        10**9,
        current_path,
        used_cells,
    )


print(best_move([""] * 9, "X"))  # (0, 0)

Common Pitfalls

  • Incorrect base cases: Check wins before checking for a full board, and score draws as 0.

  • Failure to undo moves: Every explored move must be restored before exploring a sibling.

  • Wrong player perspective: minimax values assume a zero-sum game with optimal opposing players.

  • Invalid pruning: Alpha-beta is unsuitable for cooperative or non-zero-sum games unless its assumptions are changed.

  • Excessive recursion depth: Python’s default recursion limit is about 1000. Tic-tac-toe is safe, but much deeper searches may require an explicit stack or another algorithm.

  • Mutating the caller’s input: Copy the board at the public API boundary, as shown above.

33

How is backtracking used in network routing optimization?

Backtracking in network routing optimization explores candidate routes by extending one path at a time, then undoing choices that violate constraints or cannot improve the incumbent. It is an exact method for small, highly constrained problems; for ordinary single-metric shortest paths, Dijkstra or A* is usually preferable.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

How It Works

  • State: Maintain the current path, a used-node set, accumulated latency, and the path’s bottleneck bandwidth.

  • Base case: When the destination is reached, save a copy of the current path if it satisfies all constraints and improves the best objective.

  • Choose: Select a feasible next hop from the current node.

  • Explore: Extend the path and recursively search from that hop.

  • Un-choose: Restore the path and used-node set before considering the next hop.

  • Pruning: Stop a branch when its latency exceeds the limit, its bottleneck bandwidth is too low, or its current latency cannot beat the best route.

These prunings are safe because link delays are nonnegative, adding links cannot increase bottleneck bandwidth, and extending a path cannot reduce its accumulated latency. Disjoint-path routing extends the state with previously selected paths, while policy routing can enforce additional edge-feasibility rules.

In the example below:

  1. A -> B is accepted with 10 ms latency and 100 Mbps bandwidth.

  2. A -> B -> C -> D is rejected because its bottleneck is only 50 Mbps.

  3. Backtracking selects A -> B -> D, which takes 25 ms and provides 80 Mbps.

Complexity and Alternatives

For n nodes and m links:

  • Best case: O(n) when the first explored route is feasible, such as on a simple chain.

  • Average case: Workload-dependent; no standard distribution-free average exists.

  • Worst case: O(n · n!), because a complete graph can contain O(n!) simple paths and each recorded result costs up to O(n).

  • Space: O(n) auxiliary space for the recursion stack, current path, and used set; the input graph is excluded, and the returned route uses O(n) space.

Approach Guarantee and time Space When to use
Backtracking Exact over enumerated simple paths; O(n · n!) worst case O(n) auxiliary Small topologies with complex constraints
Dijkstra / A* Exact for one additive nonnegative metric; typically O((n + m) log n) O(n + m) including the graph Ordinary shortest paths
Expanded-state shortest path Exact for discretized constraint states; O(S log S) for S states O(S) Constraints have manageable discrete budgets
Metaheuristic No general optimality guarantee; implementation-dependent Implementation-dependent Large networks needing fast approximate solutions

Code Example

from collections.abc import Mapping, Sequence

Graph = Mapping[str, Sequence[tuple[str, float, int]]]


def find_best_route(
    graph: Graph,
    source: str,
    destination: str,
    max_latency_ms: float,
    min_bandwidth_mbps: int,
) -> tuple[str, ...] | None:
    """Return the minimum-latency simple route satisfying both constraints."""
    if max_latency_ms < 0:
        raise ValueError("Maximum latency must be non-negative")
    if min_bandwidth_mbps <= 0:
        raise ValueError("Minimum bandwidth must be positive")

    for links in graph.values():
        for _, delay_ms, bandwidth_mbps in links:
            if delay_ms < 0 or bandwidth_mbps < 0:
                raise ValueError("Link delay and bandwidth must be non-negative")

    current_path = [source]
    used_nodes = {source}
    best_path: list[str] | None = None
    best_latency_ms = float("inf")

    def search(
        current_node: str,
        latency_ms: float,
        bottleneck_mbps: float,
    ) -> None:
        nonlocal best_path, best_latency_ms

        # Base case: save a copy of a feasible route.
        if current_node == destination:
            if latency_ms < best_latency_ms:
                best_latency_ms = latency_ms
                best_path = current_path.copy()
            return

        # Pruning: nonnegative remaining delays cannot improve this branch.
        if latency_ms >= best_latency_ms:
            return

        for next_node, edge_delay_ms, edge_bandwidth_mbps in graph.get(
            current_node, ()
        ):
            next_latency_ms = latency_ms + edge_delay_ms
            next_bottleneck_mbps = min(
                bottleneck_mbps, float(edge_bandwidth_mbps)
            )

            if next_latency_ms > max_latency_ms:
                continue
            if next_bottleneck_mbps < min_bandwidth_mbps:
                continue
            if next_node in used_nodes:
                continue

            # Choose
            current_path.append(next_node)
            used_nodes.add(next_node)

            # Explore
            search(next_node, next_latency_ms, next_bottleneck_mbps)

            # Un-choose
            used_nodes.remove(next_node)
            current_path.pop()

    search(source, 0.0, float("inf"))
    return tuple(best_path) if best_path is not None else None


graph = {
    "A": [("B", 10.0, 100), ("C", 20.0, 50)],
    "B": [("C", 5.0, 50), ("D", 15.0, 80)],
    "C": [("D", 10.0, 100)],
    "D": [],
}

print(find_best_route(graph, "A", "D", 30.0, 60))
# Expected output: ('A', 'B', 'D')

Common Pitfalls and Interview Tips

  • Edge cases: A missing source or disconnected graph returns None; a one-node route such as ('A',) is returned when source and destination match; parallel links are separate choices; negative delay or bandwidth values are invalid and rejected; link order affects pruning order but not correctness; cycles are excluded by the used set.

  • Use an epsilon only for soft floating-point comparisons. A hard latency limit should not be violated merely to accommodate rounding error.

  • Memoization keys must include every relevant budget, resource, and policy state, not just the node and one residual budget.

  • If path depth can exceed roughly 1,000 hops, use an explicit stack or raise Python’s recursion limit.

  • Production routers generally use CSPF or specialized constrained-path algorithms; backtracking is more realistic in offline planning, validation, and small subproblems.

34

How can backtracking optimize database query plans?

Backtracking lets a database optimizer explore alternative execution plans while pruning branches that cannot beat the best plan found so far. It is especially useful for join ordering, index selection, join algorithms, and other cost-based optimization decisions.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Backtracking in a Query Optimizer

A query optimizer often has several valid plans for the same SQL query. For example, three tables might be joined in several orders, and each order might use different indexes or join algorithms.

The optimizer builds a search tree:

  1. Choose an unselected relation or access path.

  2. Explore plans that extend the partial plan.

  3. Estimate the complete plan’s cost using statistics, cardinalities, selectivity, and I/O models.

  4. Unchoose the relation and restore the previous state.

  5. Keep the lowest-cost complete plan.

Backtracking is usually combined with branch-and-bound: once a partial plan’s cost plus a safe lower bound is no better than the best complete plan, that branch is abandoned.

Production optimizers often use dynamic programming or specialized bushy-join algorithms for large numbers of relations, but backtracking and branch-and-bound remain important for small searches and complex plan spaces.

Search State and Pruning

For join ordering, useful state includes:

  • Current path: relations joined so far and their order.

  • Used set: relations already included, preventing duplicates.

  • Start index: the next position in the current path.

  • Partial cost: estimated cost accumulated by the current join sequence.

  • Base case: every relation has been selected and the complete plan is evaluated.

Pruning can use:

  • Cost bounds: abandon a partial plan whose cost already exceeds the best plan.

  • Lower bounds: estimate unavoidable future costs.

  • Cardinality bounds: reject plans that cannot satisfy required selectivity or join conditions.

  • Dominance: discard a state when another state with the same joined set has no greater cost.

For a left-deep join order, each future relation adds one join edge. Summing the cheapest incident edge for each unused relation provides a safe lower bound because every actual future edge costs at least that relation’s minimum incident cost.

Approach Time Auxiliary space When to use
Unpruned permutation search (O(n cdot n!)) (O(n)) Very small join counts or teaching
Branch-and-bound backtracking Worst (O(n cdot n!)) (O(n)) Production-style exact search with useful estimates

Complexity

For (n) relations:

  • Best case: (O(n^2)) in this implementation when the first complete plan is optimal and remaining branches are pruned.

  • Average case: no universal distribution; (O(n cdot n!)) when pruning provides little benefit.

  • Worst case: (O(n cdot n!)), because the search space contains (n!) permutations and each node may scan (n) candidates.

  • Space: (O(n)) auxiliary space, including the recursion stack, current path, and used set. The input cost table is excluded; counting that (O(n^2)) input makes total storage (O(n^2)).

The search space is factorial, or superexponential, in the number of relations.

Code Example

This toy optimizer finds the lowest-cost left-deep join order. Missing pair costs are treated as forbidden joins.

from math import inf, isnan


def optimize_join_order(
    relations: tuple[str, ...],
    join_costs: dict[tuple[str, str], float],
) -> tuple[str, ...]:
    """Return the lowest-cost left-deep join order."""
    if len(set(relations)) != len(relations):
        raise ValueError("Relation names must be unique.")
    if not relations:
        return ()
    if len(relations) == 1:
        return relations

    relation_count = len(relations)
    normalized_costs: dict[tuple[str, str], float] = {}

    # Normalize pair costs and make them symmetric.
    for left_index in range(relation_count):
        left = relations[left_index]
        for right_index in range(left_index + 1, relation_count):
            right = relations[right_index]
            pair = (left, right)
            reverse_pair = (right, left)

            if pair in join_costs:
                cost = join_costs[pair]
            elif reverse_pair in join_costs:
                cost = join_costs[reverse_pair]
            else:
                cost = inf

            if isnan(cost) or cost < 0:
                raise ValueError("Join costs must be non-negative numbers.")

            normalized_costs[pair] = cost
            normalized_costs[reverse_pair] = cost

    minimum_incoming_cost = {
        relation: min(
            normalized_costs[(relation, other)]
            for other in relations
            if other != relation
        )
        for relation in relations
    }

    best_plan: tuple[str, ...] | None = None
    best_cost: float | None = None

    def search(
        current_path: list[str],
        used_set: set[str],
        start_index: int,
        partial_cost: float,
    ) -> None:
        nonlocal best_plan, best_cost

        # Base case: every relation has been selected.
        if start_index == relation_count:
            if partial_cost < inf and (
                best_cost is None or partial_cost < best_cost
            ):
                best_plan = tuple(current_path)
                best_cost = partial_cost
            return

        # Prune with a safe lower bound on future join costs.
        if best_cost is not None:
            lower_bound = sum(
                minimum_incoming_cost[relation]
                for relation in relations
                if relation not in used_set
            )
            if partial_cost + lower_bound >= best_cost:
                return

        for relation in relations:
            if relation in used_set:
                continue

            if current_path:
                next_cost = (
                    partial_cost
                    + normalized_costs[(current_path[-1], relation)]
                )
            else:
                next_cost = 0.0

            if next_cost == inf:
                continue

            # Choose the next relation.
            current_path.append(relation)
            used_set.add(relation)

            # Explore plans containing this choice.
            search(current_path, used_set, start_index + 1, next_cost)

            # Undo the choice.
            used_set.remove(relation)
            current_path.pop()

    search([], set(), 0, 0.0)

    if best_plan is None:
        raise ValueError("No finite-cost join order exists.")

    return best_plan


costs = {
    ("orders", "customers"): 10,
    ("orders", "products"): 100,
    ("customers", "products"): 5,
}

print(optimize_join_order(("orders", "customers", "products"), costs))
# ('orders', 'customers', 'products')

The winning path is:

Step Join Added cost Total
1 Select orders 0 0
2 Join customers 10 10
3 Join products 5 15

Common Pitfalls

  • Unsafe pruning: A lower bound must never exceed the cheapest possible completion.

  • Duplicate relations: Track used relations explicitly.

  • Incorrect base case: Evaluate only when all required relations are present.

  • Mutable state: Undo every choice so sibling branches start from the same state.

  • Edge cases: Empty input returns an empty plan; one relation requires no joins; duplicate names and negative costs raise errors; disconnected join graphs may have no valid plan; cycles in the join graph do not affect this algorithm.

  • Estimator limitations: The optimizer finds the cheapest plan according to its cost model, not necessarily the fastest plan under real workloads. Interviewers commonly ask how cardinality errors, indexes, parallelism, and bushy join trees affect the result.

35

How does backtracking solve scheduling and planning problems?

Backtracking solves scheduling and planning problems by building a partial plan incrementally, exploring each legal choice, and undoing choices that cannot lead to a feasible schedule. It is most effective when constraints allow substantial pruning of the search space.

Read full answer

Applies tolanguage-independent (examples in Python 3.12)

Core Approach

A scheduling problem can be modeled as a sequence of decisions:

  1. Choose the next task, shift, assignment, or route segment.

  2. Explore the resulting partial plan.

  3. Un-choose it if a later decision fails.

The search state normally contains:

  • Current path: the task indexes selected so far, in execution order.

  • Used set: tasks already committed to the schedule.

  • Current time: when the next task can start.

  • Start index: no monotonic start_index is used here because a previously skipped task may become eligible after one of its dependencies is scheduled.

The base case is reached when every required task has been scheduled. The search then returns the completed plan.

Common constraints and pruning rules include:

  • Precedence: skip a task until all its dependencies have been scheduled.

  • Deadlines: reject a candidate whose completion time exceeds its deadline; later tasks cannot make that candidate finish earlier.

  • Release times: delay a candidate until its earliest permitted start time.

  • Resources: reject assignments that exceed capacity or reuse an occupied resource.

  • Objectives: retain the best feasible plan by cost or duration when optimization, rather than merely feasibility, is required.

For the example below, the search proceeds as follows:

Step Decision Completion time Result
1 Choose A 1 Continue
2 Choose B 2 Continue
3 Choose C after A and B 3 All tasks scheduled
4 Base case — Return schedule

Complexity and Limits

Let n be the number of distinguishable tasks and m the total number of dependency entries.

Case Time Reason
Best O(n(n + m)) The first candidate ordering succeeds, but each of n levels scans candidates and dependencies.
Average Constraint-dependent; O((n + m)n!) is a conservative upper bound The expected explored portion depends on how constraints interact with pruning.
Worst O((n + m)n!) Up to n! partial orderings may be explored, with candidate and dependency checks at each state.

The unpruned search space is factorial—more precisely, superexponential rather than polynomial. With constant-size dependency checks, the common worst-case bound is O(n * n!).

Auxiliary space is O(n), including the recursion stack, current path, used set, and copied result. The input itself is not counted.

This implementation returns the first feasible schedule. To obtain the minimum-cost schedule, search all feasible branches and retain the best result.

Code Example

from collections.abc import Sequence
from dataclasses import dataclass


@dataclass(frozen=True)
class Task:
    name: str
    duration: int
    deadline: int
    earliest_start: int = 0
    dependencies: tuple[int, ...] = ()


@dataclass(frozen=True)
class ScheduledTask:
    name: str
    start: int
    end: int


def schedule_tasks(tasks: Sequence[Task]) -> list[ScheduledTask] | None:
    """Return the first feasible task schedule, or None if none exists."""
    task_count = len(tasks)

    for index, task in enumerate(tasks):
        if task.duration <= 0:
            raise ValueError("Task duration must be positive.")
        if task.earliest_start < 0:
            raise ValueError("Task earliest_start cannot be negative.")
        if task.deadline < task.earliest_start + task.duration:
            raise ValueError(f"Task {task.name!r} cannot meet its deadline.")

        for dependency in task.dependencies:
            if dependency < 0 or dependency >= task_count:
                raise ValueError(f"Task {task.name!r} has an invalid dependency.")
            if dependency == index:
                raise ValueError(f"Task {task.name!r} cannot depend on itself.")

    current_path: list[int] = []
    current_schedule: list[ScheduledTask] = []
    used: set[int] = set()

    def backtrack(current_time: int) -> bool:
        # Base case: every task has been scheduled.
        if len(current_path) == task_count:
            return True

        for index, task in enumerate(tasks):
            if index in used:
                continue

            # Reconsider this task after its dependencies are scheduled.
            if any(dependency not in used for dependency in task.dependencies):
                continue

            start = max(current_time, task.earliest_start)
            end = start + task.duration

            # Prune: later decisions cannot repair this deadline violation.
            if end > task.deadline:
                continue

            # Choose the candidate.
            used.add(index)
            current_path.append(index)
            current_schedule.append(
                ScheduledTask(name=task.name, start=start, end=end)
            )

            # Explore the resulting partial schedule.
            if backtrack(end):
                return True

            # Un-choose the candidate.
            current_schedule.pop()
            current_path.pop()
            used.remove(index)

        return False

    if not backtrack(0):
        return None

    return current_schedule.copy()


if __name__ == "__main__":
    example_tasks = [
        Task("A", duration=1, deadline=2),
        Task("B", duration=1, deadline=2),
        Task("C", duration=1, deadline=4, dependencies=(0, 1)),
    ]

    result = schedule_tasks(example_tasks)
    assert result is not None
    print([(task.name, task.start, task.end) for task in result])
    # Expected output: [('A', 0, 1), ('B', 1, 2), ('C', 2, 3)]

Common Pitfalls and Edge Cases

  • Off-by-one errors: Treat a task starting at s with duration d as ending at s + d; it meets a deadline only when end <= deadline.

  • Mutable state: Remove or copy a candidate before exploring another branch; never retain the same mutable path for multiple results.

  • Weak pruning: Check deadlines and capacity as soon as a decision is made rather than waiting until the complete schedule.

  • Recursion depth: This recursive version assumes n is below Python’s default recursion limit, approximately 1000. Use an explicit stack or carefully raise the limit for larger inputs.

  • Overflow in fixed-width languages: Use sufficiently wide integers for large times and costs.

  • Empty input: schedule_tasks([]) returns an empty schedule.

  • One task: It is scheduled when its release time and deadline permit it.

  • Duplicates: Equal task records are distinct when referenced by index.

  • Negative values: Negative durations and release times are rejected.

  • Already sorted input: Input order affects which feasible schedule is found first, but not correctness.

  • Disconnected dependency graphs: Independent components can be scheduled in the same plan.

  • Dependency cycles: Cyclic dependencies have no valid ordering, so the search returns None.

Sign in to keep reading

You've opened 2 full answers. Sign in to read all 35 Backtracking answers, mark what you know and pick up where you left off.

Report a mistake

What's wrong?

All Data Structures & Algorithms subjects