Backtracking Pattern

Backtracking is a general algorithmic technique that builds solutions incrementally, one piece at a time, and abandons ("backtracks") a path as soon as it determines the path cannot lead to a valid solution. It's essentially a refined brute-force search with early pruning.

Decision tree for subsets of [1, 2, 3]:

                    []
              /            \
          [1]                []
        /      \           /     \
     [1,2]    [1]       [2]      []
     /  \    /  \      /  \    /  \
  [1,2,3] [1,2] [1,3] [1] [2,3] [2] [3] []

Core Concept

Every backtracking problem follows the same template: choose, explore, unchoose.

function backtrack(state, choices):
    if state is a valid solution:
        record solution
        return

    for each choice in choices:
        if choice is valid:
            make choice          ← CHOOSE
            backtrack(new state) ← EXPLORE
            undo choice          ← UNCHOOSE (backtrack)

The key insight is that we're traversing a decision tree where each node represents a partial solution and each branch represents adding one more element. We prune entire subtrees when we detect that a path can't lead to a valid solution.

Key Techniques

1. Subsets (Include/Exclude)

For each element, decide: include it or skip it. This generates all 2^n subsets.

function subsets(nums):
    result = []
    function backtrack(index, current):
        if index == nums.length:
            result.add(copy of current)
            return
        // Include nums[index]
        current.push(nums[index])
        backtrack(index + 1, current)
        current.pop()  ← backtrack
        // Exclude nums[index]
        backtrack(index + 1, current)
    backtrack(0, [])

2. Combinations (With Constraints)

Like subsets, but with a target constraint (e.g., sum = target). Prune when the remaining sum is impossible. Elements can sometimes be reused (start from same index instead of next).

function combinationSum(candidates, target):
    function backtrack(index, current, remaining):
        if remaining == 0: record solution
        if remaining < 0: return (prune)
        for i from index to end:
            current.push(candidates[i])
            backtrack(i, current, remaining - candidates[i])  ← same index for reuse
            current.pop()  ← backtrack

3. Permutations (Ordering Matters)

Generate all orderings. Track which elements are "used" to avoid duplicates.

function permute(nums):
    function backtrack(current, used):
        if current.length == nums.length: record solution
        for i from 0 to end:
            if not used[i]:
                used[i] = true
                current.push(nums[i])
                backtrack(current, used)
                current.pop()    ← backtrack
                used[i] = false  ← backtrack

4. Grid-Based Backtracking

DFS on a grid with visited tracking. Each cell explores 4 directions and backtracks by unmarking.

function exist(board, word):
    function dfs(row, col, index):
        if index == word.length: return true
        if out of bounds or board[row][col] != word[index]: return false
        temp = board[row][col]
        board[row][col] = '#'  ← mark visited
        found = dfs(row+1,col,index+1) or dfs(row-1,col,index+1) or ...
        board[row][col] = temp ← backtrack
        return found

5. Constraint Satisfaction (N-Queens)

Place items under constraints. Track which positions are invalid and prune aggressively.

function nQueens(n):
    function backtrack(row, cols, diag1, diag2):
        if row == n: record solution
        for col in 0..n-1:
            if col not in cols and (row-col) not in diag1 and (row+col) not in diag2:
                place queen, add constraints
                backtrack(row + 1, ...)
                remove queen, remove constraints  ← backtrack

Common Mistakes

1. Forgetting to undo state changes — The "unchoose" step is critical. If you push to an array but forget to pop after recursion, all branches share corrupted state.
2. Passing references instead of copies — When recording a solution, you must copy the current array (e.g., result.push([...current])). Otherwise, all recorded solutions point to the same mutated array.
3. Wrong loop start index — For combinations without duplicates, start the loop at the current index (not 0). Starting at 0 produces duplicate combinations like [1,2] and [2,1].
4. Missing base case or pruning — Without proper termination, backtracking becomes brute force. Prune early: if remaining sum < 0, if index out of bounds, if constraints are violated.
5. Not restoring grid cells after DFS — In grid-based problems, if you mark a cell visited but don't unmark it after returning, other paths can't use that cell. Always restore: board[r][c] = temp.