Advanced Recursion and Backtracking Interview Patterns: N-Queens, Sudoku, Expression Add Operators (2025)

Backtracking Framework

Backtracking = DFS + pruning. The general framework: choose a candidate for the next position, recurse, undo the choice (backtrack). Prune when a partial solution cannot possibly lead to a valid complete solution. The key to efficient backtracking is strong pruning — eliminating branches early avoids exponential blowup. Time complexity is always exponential in the worst case but varies dramatically based on pruning quality. When to use backtracking: problems asking for all valid configurations, all paths, or one valid configuration out of a combinatorial space.

Pattern 1: N-Queens (LC 51)

Place N queens on an N×N board such that no two queens attack each other. Constraint: no two queens share the same row, column, or diagonal. Backtracking approach: place one queen per row. For each row, try each column. Check constraints before placing: a column is valid if no previously placed queen uses it; diagonals are valid if no queen is on the same (row-col) or (row+col) diagonal. Track used columns and diagonals in sets for O(1) lookup.

def solve_n_queens(n):
    results = []
    cols = set()
    diag1 = set()  # row - col constant
    diag2 = set()  # row + col constant

    def backtrack(row, board):
        if row == n:
            results.append(["".join(r) for r in board])
            return
        for col in range(n):
            if col in cols or (row-col) in diag1 or (row+col) in diag2:
                continue
            cols.add(col); diag1.add(row-col); diag2.add(row+col)
            board[row][col] = 'Q'
            backtrack(row + 1, board)
            board[row][col] = '.'
            cols.remove(col); diag1.remove(row-col); diag2.remove(row+col)

    backtrack(0, [['.']*n for _ in range(n)])
    return results

Pattern 2: Sudoku Solver (LC 37)

Fill a 9×9 Sudoku grid. Constraints: each row, column, and 3×3 box contains digits 1-9 exactly once. Backtracking: find the first empty cell. Try digits 1-9. For each digit: check if it’s valid (not in the row, column, or box). Place it and recurse. If recursion fails: remove the digit and try the next. Pruning optimization: instead of picking the first empty cell, pick the empty cell with the fewest valid options (Minimum Remaining Values heuristic). This dramatically reduces the search tree. Constraint propagation (AC-3 algorithm) can eliminate options before backtracking even begins — used by the fastest Sudoku solvers.

def solve_sudoku(board):
    def is_valid(r, c, d):
        if d in [board[r][i] for i in range(9)]: return False
        if d in [board[i][c] for i in range(9)]: return False
        br, bc = 3*(r//3), 3*(c//3)
        if d in [board[br+i][bc+j] for i in range(3) for j in range(3)]: return False
        return True

    def backtrack():
        for r in range(9):
            for c in range(9):
                if board[r][c] != '.': continue
                for d in '123456789':
                    if is_valid(r, c, d):
                        board[r][c] = d
                        if backtrack(): return True
                        board[r][c] = '.'
                return False  # no valid digit found
        return True  # all cells filled

    backtrack()

Pattern 3: Expression Add Operators (LC 282)

Given a string of digits, insert +, -, * operators between digits to make the expression equal to a target value. The challenge: multiplication has precedence over addition/subtraction. Track the last operand to handle multiplication correctly: when you multiply, undo the previous addition of the last operand and add last * current instead.

def add_operators(num, target):
    results = []

    def backtrack(idx, path, val, last):
        if idx == len(num):
            if val == target: results.append(path)
            return
        for i in range(idx, len(num)):
            s = num[idx:i+1]
            if len(s) > 1 and s[0] == '0': break  # no leading zeros
            n = int(s)
            if idx == 0:
                backtrack(i+1, s, n, n)
            else:
                backtrack(i+1, path+'+'+s, val+n, n)
                backtrack(i+1, path+'-'+s, val-n, -n)
                backtrack(i+1, path+'*'+s, val-last+last*n, last*n)

    backtrack(0, '', 0, 0)
    return results

The last parameter tracks the last operand so multiplication can “undo” the previous addition. This is the key insight — without it, precedence handling is impossible in a single pass.

Pattern 4: Palindrome Partitioning (LC 131) and Combination Sum

Palindrome Partitioning: partition a string into substrings that are all palindromes. Backtracking: at each position, try extending to the next palindromic substring. Precompute palindrome check with DP (is_palindrome[i][j]) to avoid redundant checks during backtracking — O(n^2) preprocessing, O(n * 2^n) total. Combination Sum (LC 39): find all combinations of candidates that sum to target. Backtracking: at each step, either use the current candidate again (allow repetition) or move to the next. Prune: if the remaining target remaining, all subsequent candidates are also too large).

{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”What is the general backtracking framework?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Backtracking is DFS with pruning: (1) choose a candidate for the next position, (2) check constraints — if violated, skip this branch (prune), (3) recurse with the candidate placed, (4) undo the choice (backtrack) and try the next candidate. Strong pruning is the key to efficiency — eliminating branches early prevents exponential blowup.”}},{“@type”:”Question”,”name”:”How do you efficiently check queen placement constraints in N-Queens?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Use three sets: one for used columns, one for used (row-col) diagonals (top-left to bottom-right), and one for used (row+col) diagonals (top-right to bottom-left). All three checks are O(1). Two queens on the same top-left diagonal have the same (row-col) value; same top-right diagonal have the same (row+col) value. This avoids O(n) column/diagonal scanning per placement.”}},{“@type”:”Question”,”name”:”How do you handle operator precedence in the expression add operators problem?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Track the last operand in the recursion. When applying multiplication: the current accumulated value includes the last operand added via +/-. To multiply: subtract the last operand (undoing its addition), then add last * current. The new last operand is last * current. This one-pass approach correctly handles * before +/- without building and evaluating a full expression tree.”}},{“@type”:”Question”,”name”:”What is the Minimum Remaining Values (MRV) heuristic in Sudoku solving?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Instead of always filling the first empty cell, MRV selects the empty cell with the fewest valid digit options remaining. A cell with only 1 valid option must use that digit — no branching needed. A cell with 2 options branches into 2 paths instead of potentially 9. MRV dramatically reduces the search tree size compared to sequential cell selection.”}},{“@type”:”Question”,”name”:”How do you prune combination sum backtracking efficiently?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Sort the candidates array first. During backtracking, if the current candidate exceeds the remaining target, all subsequent candidates (which are larger) will also exceed it — break the loop immediately. This converts O(n) per level pruning into an early-exit that skips entire subtrees. Also, start each recursive call from the current index (not 0) to avoid duplicate combinations.”}}]}