Backtracking in the Real World

Backtracking is more than an interview technique. It runs inside tools you use every day: regular expression engines, SAT solvers, constraint programming libraries, and logic programming languages. This chapter covers where it shows up, the pitfalls you meet in production code, and where to read more.

Where backtracking runs

• Regular expression engines: Python re, Java java.util.regex, JavaScript, and PCRE try each alternative of a pattern (|, *, +) in turn and back up on failure. That is what makes features like backreferences possible, and also why some inputs take exponential time.
• SAT solvers and DPLL: the DPLL algorithm assigns Boolean variables one at a time and backtracks on a contradiction. It is the foundation of modern CDCL SAT solvers used in hardware verification and package dependency resolution.
• Constraint programming: solvers such as Google OR-Tools CP-SAT model timetables, shift rosters, and production schedules as variables and constraints, and use constraint propagation to prune branches before exploring them.
• Logic programming: in Prolog, trying rules from the top and falling back to the next rule on failure is the execution model itself.
• Puzzles and games: Sudoku, crossword, and exact cover solvers (Knuth's Dancing Links) are classic examples.
• Parsers: PEG parsers and some recursive descent parsers try grammar alternatives in order and rewind the input position when one fails.

Pitfall 1: catastrophic backtracking in regexes

A pattern like (a+)+$ can split a run of a characters in exponentially many ways, so on input whose ending does not match, the engine tries every split. Applying such a pattern to user-supplied text opens the door to a denial-of-service attack (ReDoS).

import re
import time

pattern = re.compile(r"(a+)+$")
for n in (16, 18, 20, 22):
    text = "a" * n + "!"
    start = time.perf_counter()
    pattern.match(text)
    print(n, f"{time.perf_counter() - start:.3f}s")
# every extra character roughly doubles the time

Fixes include removing the nested repetition (a+$ matches the same strings here), limiting input length, or switching to an engine with linear-time guarantees such as RE2.

Pitfall 2: recursion depth and copying

Python's default recursion limit is around 1000, so searches thousands of levels deep raise RecursionError. You can raise the limit with sys.setrecursionlimit, but that risks overflowing the C stack; for deep searches an explicit stack is safer.

def subsets_iterative(nums):
    result = []
    stack = [(0, [])]                 # (next index, partial solution)
    while stack:
        i, path = stack.pop()
        if i == len(nums):
            result.append(path)
            continue
        stack.append((i + 1, path))               # branch that skips nums[i]
        stack.append((i + 1, path + [nums[i]]))   # branch that takes it
    return result

print(subsets_iterative([1, 2]))  # [[1, 2], [1], [2], []]