Skip to content
Hello Python
Algorithm1 Practice13 Interview

Backtracking

Enumerate constrained candidates by choosing, exploring, pruning, and undoing decisions. Learn the algorithm's preconditions, state transition, correctness argument, Python cost model, and transfer from one focused drill to a full Interview Problem.

Recognize it when

Consider Backtracking when the prompt's constraints and required operations match this shape: Enumerate constrained candidates by choosing, exploring, pruning, and undoing decisions.

Pybit demonstrates Backtracking in a professional Python interview workspace.
On this page · Search a Decision Tree

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Backtracking Code Labs

Search a Decision Tree

Backtracking explores a tree whose nodes are partial candidates and whose edges are choices. A solution is recorded only when the path satisfies the terminal contract.

Choose Apply Explore Undo

For each choice: apply it to the current path, explore the smaller remaining problem, then undo exactly that mutation. Copy only when recording output; otherwise share one path and restore it before the next sibling.

Trace Apply Explore Undo

Reference
def binary_choice_trace(length):
    events = []
    path = []
    def search():
        if len(path) == length: return
        for choice in (0, 1):
            path.append(choice)
            events.append(["choose", path.copy()])
            search()
            events.append(["undo", path.copy()])
            path.pop()
    search()
    return events
Practice

Implement binary_choice_trace(length). Return ["choose", path] and ["undo", path] events while exploring 0 before 1 to the requested length.

Public tests

  • Restore path after every branch

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Prune Only with Proof

A prune is correct only when no completion below the current state can succeed. Sort choices to enable duplicate skipping or monotone bounds, and distinguish “skip this duplicate at this depth” from banning a value globally.

Build Unique Combinations

Reference
def unique_combinations(values, width):
    values = sorted(values)
    result = []
    path = []
    def search(start):
        if len(path) == width:
            result.append(path.copy())
            return
        for index in range(start, len(values)):
            if index > start and values[index] == values[index - 1]: continue
            path.append(values[index])
            search(index + 1)
            path.pop()
    search(0)
    return result
Practice

Implement unique_combinations(values, width). Return lexicographically ordered unique combinations of the requested width; each input index is used at most once.

Public tests

  • Skip duplicate choices at one depth

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Choose Backtracking or Dynamic Programming

Use backtracking when outputs or constraints require enumerating distinct decision paths. Use dynamic programming when many paths reach the same state and only an aggregate answer is needed. Worst-case backtracking is usually exponential plus output-copy cost.

Explain It in an Interview

Say: “The path contains exactly the choices made so far. I apply one legal choice, recurse, and undo it so siblings start from identical state. This prune is safe because…” Then state branching factor, maximum depth, and output cost. Reusable-Candidate Combination Sum(opens in a new tab) exercises these decisions.

Python Version Note

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

OperationAverageWorstInterview note
Backtracking complete workflowO(c * (p + 1))O(c * (p + 1))Each backtracking branch needs a path state that includes one choice but does not leak that choice into sibling branches. Before expanding each choice, path equals the original caller-owned prefix; every emitted candidate contains exactly one additional element.

Space

O(c * (p + 1)) for independent candidates for the focused Complete One Backtracking Frame implementation.

Assumptions

  • Appending one choice creates exactly one candidate extension, and copying it prevents later mutations from changing prior output. Popping restores the original path before the next choice, so all and only one-step branches are emitted.
  • The bound counts Python sorting, slicing, hashing, heap, recursion, and container-copy costs rather than treating syntax as free.

Invariants Worth Saying Aloud

  1. State the precise Backtracking invariant before coding and preserve it after every update, traversal step, or recursive return.
  2. The call arguments fully describe the current subproblem.
  3. Every recursive branch either reaches a base case or strictly reduces the remaining work.
  4. Each backtracking branch needs a path state that includes one choice but does not leak that choice into sibling branches. Preserve this claim after every transition.
  5. Before expanding each choice, path equals the original caller-owned prefix; every emitted candidate contains exactly one additional element. Preserve this claim after every transition.

When To Use Or Avoid Backtracking

Use It When

  • Use Backtracking when this precondition is stated or can be proved: Every recursive call reduces a well-defined measure and all terminal states have explicit base cases.
  • Use it when this maintained state removes repeated work: The call arguments fully describe the current subproblem.

Choose Another Tool When

  • Avoid Backtracking when this precondition is absent: Every recursive call reduces a well-defined measure and all terminal states have explicit base cases.
  • Avoid it when a simpler direct scan satisfies the constraints with less implementation risk.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Applying the algorithm without its precondition

Verify algorithm preconditions such as sorted input, nonnegative weights, acyclicity, or admissible heuristics before applying it.

Prevent it: State and verify this precondition before coding: Every recursive call reduces a well-defined measure and all terminal states have explicit base cases.

Avoid

def expand_backtracking_frame(path, choices):
    pass

Use instead

def expand_backtracking_frame(path, choices):
    candidates = []
    for choice in choices:
        path.append(choice)
        candidates.append(path.copy())
        path.pop()
    return candidates

Where you will hit this: Complete One Backtracking Frame(opens in a new tab)

Breaking the state transition

Never undoes the choice and stores the same mutable path object for every sibling candidate.

Prevent it: Preserve this proof obligation: The decreasing measure guarantees termination, and each return preserves the contract of its smaller subproblem.

Avoid

def expand_backtracking_frame(path, choices):
    candidates = []
    for choice in choices:
        path.append(choice)
        candidates.append(path)
    return candidates

Use instead

def expand_backtracking_frame(path, choices):
    candidates = []
    for choice in choices:
        path.append(choice)
        candidates.append(path.copy())
        path.pop()
    return candidates

Where you will hit this: Complete One Backtracking Frame(opens in a new tab)

Hiding Python work in the claimed bound

Include visited state, boundary cases, recursion depth, and hidden copying costs in correctness and complexity analysis.

Prevent it: Count every sort, slice, copy, membership check, heap update, and recursive frame before claiming O(c * (p + 1)).

Avoid

def expand_backtracking_frame(path, choices):
    candidates = []
    for choice in choices:
        path.append(choice)
        candidates.append(path)
    return candidates

Use instead

def expand_backtracking_frame(path, choices):
    candidates = []
    for choice in choices:
        path.append(choice)
        candidates.append(path.copy())
        path.pop()
    return candidates

Where you will hit this: Reusable-Candidate Combination Sum(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.