Dashboard/Coding patterns/12. Backtracking

CODING PATTERNS · LESSON 12 OF 28 · 62 MIN VIDEO · 20 PROBLEMS

Backtracking

Module Progress (0 / 20 Problems Solved)0%
Coding patterns Track (0 / 28 Modules) · Overall 0/80 (0%)0%
⌁

Narrated HD Video Lesson (62 min) · Pro

Pattern Guide + Problem #01 + Checkpoint Quiz #1 are unlocked free below (no login required). Unlock all 80 HD video lessons and all 540 Python problems — or watch our two free sample video lessons first.

PATTERN STUDY GUIDE

Backtracking — How the Pattern Works

Backtracking is a systematic depth-first search paradigm that constructs candidate solutions incrementally through a sequence of choices, abandoning any partial state the moment it violates problem constraints. At every recursive step, it maintains a single shared mutable state (such as a partial list, board, or visited marker) under the choose-explore-undo invariant: mutate the state before recursing and restore it immediately upon return so sibling branches observe an untouched prefix. By pruning invalid or suboptimal branches at internal nodes of the decision tree rather than generating and validating complete configurations at the leaves, backtracking slashes combinatorial search spaces (e.g., O(C(n^2, n)) to O(n!) in N-Queens, or O(2^n) to O(n^3) when initial choices force the remainder) while keeping auxiliary state space proportional to the recursion depth O(d).

WHEN TO USE THIS PATTERN
  • Prompts asking to enumerate all valid configurations, paths, subsets, combinations, or string partitions rather than returning a single greedy value.
  • Constraint-satisfaction puzzles on 2D grids or boards (N-Queens, Sudoku, Word Search, Unique Paths III) where placing an item or visiting a cell restricts subsequent choices and can hit dead ends.
  • Small input bounds (n <= 15 to 20, grid size <= 9 x 9, or k <= 10) signaling an exponential or factorial decision tree paired with aggressive constraint or branch-and-bound pruning.
  • Optimization problems lacking greedy-choice or polynomial-state DP structure (such as equal-sum bin packing in Matchsticks to Square or debt settlement in Optimal Account Balancing) where early assignments constrain future feasibility.
  • Tree or DAG path-enumeration tasks where routes share common prefixes and a single mutable path list can be grown on descent and popped on return.
COMMON INTERVIEW PITFALLS
  • Appending the live mutable path reference (result.append(path)) instead of a snapshot copy (result.append(list(path)) or "".join(path)), leaving every recorded entry empty once backtracking unwinds.
  • Forgetting to undo in-place state mutations (restoring board[r][c], removing keys from conflict sets, or reverting bucket sums) before returning, which corrupts state for subsequent sibling branches.
  • Using a global visited set across the entire search when enumerating all paths in a graph or grid, which permanently blocks shared downstream nodes after the first path visits them instead of only blocking cycles along the active path.
  • Validating rules only at leaf nodes or omitting symmetry-breaking invariants (passing i + 1 for combinations, sorting items descending in bin packing, or skipping adjacent duplicate deletions), resulting in redundant O(n!) exploration.
Canonical Combination & Partition Backtracking (Choose-Explore-Undo)Enumerating unordered combinations, valid splits, or constrained sequences in canonical order while pruning invalid partial candidates immediately.
def backtrack_combinations(candidates, k):
    result, path = [], []
    def dfs(start):
        if len(path) == k:
            result.append(list(path))
            return
        for i in range(start, len(candidates)):
            if is_valid(candidates[i], path):
                path.append(candidates[i])
                dfs(i + 1)
                path.pop()
    dfs(0)
    return result
2D Grid Path & Constraint Search (In-Place Mark & Unmark)Tracing non-self-intersecting paths or filling constrained cells on a grid without allocating per-branch visited sets.
def grid_backtrack(grid, r, c, idx, target):
    if idx == len(target):
        return True
    if not (0 <= r < len(grid) and 0 <= c < len(grid[0])) or grid[r][c] != target[idx]:
        return False
    saved, grid[r][c] = grid[r][c], "#"
    found = any(grid_backtrack(grid, r + dr, c + dc, idx + 1, target)
                for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)))
    grid[r][c] = saved
    return found
Row-by-Row Placement with O(1) Conflict SetsPlacing non-attacking or mutually exclusive items across rows, columns, and diagonals/boxes in O(1) validation time per candidate.
def count_placements(n):
    cols, diag, anti = set(), set(), set()
    def dfs(r):
        if r == n:
            return 1
        ways = 0
        for c in range(n):
            if c not in cols and r - c not in diag and r + c not in anti:
                cols.add(c); diag.add(r - c); anti.add(r + c)
                ways += dfs(r + 1)
                cols.remove(c); diag.remove(r - c); anti.remove(r + c)
        return ways
    return dfs(0)
Branch-and-Bound Optimization BacktrackingFinding a minimum-cost assignment or maximum-count partition when an optimistic bound can prune branches that cannot improve upon the best answer found so far.
def branch_and_bound(items):
    best = float("inf")
    def dfs(i, cost):
        nonlocal best
        if cost >= best or i == len(items):
            best = min(best, cost) if i == len(items) else best
            return
        for choice, delta in valid_choices(items[i]):
            apply_choice(choice)
            dfs(i + 1, cost + delta)
            undo_choice(choice)
    dfs(0, 0)
    return best
🔒 PRO PROBLEMTarget: O(n · 2ⁿ) worst case

12. Remove Invalid Parentheses

Pattern Trigger: fewest edits, all fixes → count, then delete

Problem #01 of every pattern lesson is unlocked free outside the paywall. Unlock all 540 Python 3.14 problems, step-by-step solution editorials, and 80 narrated HD video lessons with Monthly ($69), 3-Month ($149), or Annual ($299) access — or 50% off for verified university students.

Pattern Checkpoint Quizzes

CHECKPOINT QUIZ #1

Same search, but now with one, two and three, each used once. How many orderings does it record?