Over a state

Use this when recursion places something into a row, cell, grid path, bucket, or slot while constraints decide whether the choice is legal.

Placement Template

dfs(pos):
    if pos == total:
        add answer
        return
 
    for choice in choices:
        if safe(pos, choice):
            place choice
            dfs(pos + 1)
            remove choice

Good constraint problems usually track enough state to make safe cheap: columns, diagonals, rows, boxes, used numbers, bucket sums, or visited cells.

Grid Path Template

dfs(r, c):
    if out of bounds or invalid or visited:
        return
 
    mark visited
    explore neighbors
    unmark visited

Common Prunes

Sort first so impossible branches can break.
Try larger numbers first for bucket-filling problems.
Skip duplicate values at the same recursion depth.
Avoid placing into equivalent empty buckets.
Stop when current sum exceeds target.
Stop when remaining choices cannot fill required size.
Use current best bounds for branch-and-bound.
Use sets or bitmasks so constraint checks are O(1).

Problems

N-Queens

Problem: place n queens on an n x n board so none attack each other.

Pattern: one queen per row; track blocked columns and diagonals.

Optimizations: use sets or bitmasks for columns and diagonals. For counting only, bitmasks are faster than mutating a board. Build board strings only when recording a full answer.

dfs(row):
    if row == n:
        ans.push(board)
        return
 
    for col = 0; col < n; col++:
        if col or diagonals are blocked:
            continue
 
        place queen
        dfs(row + 1)
        remove queen

Sudoku Solver

Problem: fill a Sudoku board.

Pattern: choose an empty cell, try digits that satisfy row, column, and box constraints. Picking the cell with the fewest candidates is a strong prune.

Optimizations: keep row, column, and box masks for O(1) candidate checks. Choose the empty cell with the fewest candidates instead of scanning left to right. Update masks during choose/undo.

Word Search

Problem: check whether a word exists as a path in a grid.

Pattern: DFS from every matching start cell, mark cells during the current path, and unmark before returning.

Optimizations: reject early if the board does not contain enough of any required character. Start from the rarer end of the word by reversing it when the last character is rarer than the first. Mark visited in-place when allowed.

dfs(r, c, i):
    if i == word.length:
        return true
 
    if out of bounds or visited or board[r][c] != word[i]:
        return false
 
    mark visited
 
    for each neighbor:
        if dfs(nr, nc, i + 1):
            return true
 
    unmark visited
    return false

Partition To K Equal Sum Subsets

Problem: split numbers into k equal-sum buckets.

Pattern: sort descending, place each number into a valid bucket, and avoid trying multiple equivalent empty buckets.

Optimizations: reject if total sum is not divisible by k or any number exceeds the target bucket sum. Sort descending. Skip buckets with the same current sum, break after trying one empty bucket, and memoize by used mask when using the bitmask formulation.

Matchsticks To Square

Problem: assign sticks into four equal sides.

Pattern: same bucket recursion as k-subsets, with four target-equal buckets.

Optimizations: reject if total sum is not divisible by 4 or the longest stick exceeds the side length. Sort descending, skip equivalent side lengths, and break after a stick fails in an empty side.

Lest I Forget

Over a State