Backtracking: One Template for 5 Problems (LC 78/39/46/79/51)

Backtracking looks like many problem types (subsets, permutations, combinations, boards…), but they all share one template:

choose → explore (recurse) → un-choose

That is: "make a choice → go down → come back and undo it → try the next choice." Only two things differ: ① how the choice space is defined (start index? used array?), and ② how to prune (cut impossible branches early). Weld this template into muscle memory and backtracking problems are just parameter swaps.

Continuing the full derivation flow:

📋 Problem → 🧭 break down → brute force → bottleneck → insight → optimum → code

• Subsets (78) → combination sum (39) → permutations (46) → word search (79) → N-Queens (51)

🧭 Universal template

def backtrack(path, choices):
    if done:
        res.append(path[:])      # collect (copy!)
        return
    for choice in choices:
        if invalid: continue     # prune
        path.append(choice)      # choose
        backtrack(path, next)    # recurse
        path.pop()               # un-choose

① LC 78 — Subsets

📋 Problem: Given an integer array nums of unique elements, return all possible subsets (the power set); no duplicate subsets.

Example: [1,2,3] → [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]

🧭 From reading the problem to the solution

1. Break it down: each element is "take / skip" — 2ⁿ combinations, a natural recursion tree.
2. Key insight: a start index enforces "only go forward," avoiding duplicates like [1,2] vs [2,1]. Every node's current path is itself a valid subset (so collect unconditionally, no need to wait for leaves).
3. Optimum: backtracking, collecting the path before recursing.

def subsets(nums):
    res = []
    def backtrack(start, path):
        res.append(path[:])                 # every node is a valid subset
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)          # i+1: no reuse, forward only
            path.pop()                      # undo
    backtrack(0, [])
    return res

void backtrack(vector<int>& nums, int start, vector<int>& path, vector<vector<int>>& res) {
    res.push_back(path);
    for (int i = start; i < (int)nums.size(); i++) {
        path.push_back(nums[i]);
        backtrack(nums, i + 1, path, res);   // i+1: forward only
        path.pop_back();
    }
}
vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> res; vector<int> path;
    backtrack(nums, 0, path, res);
    return res;
}

• Complexity: O(n · 2ⁿ) time (2ⁿ subsets, each O(n) to copy), O(n) recursion space.
• Pitfall: ① the start index prevents duplicate combinations; ② collect with path[:] (copy), or you store a reference that later mutates; ③ subsets collect at "every node," permutations collect only at leaves.

② LC 39 — Combination Sum

📋 Problem: Given distinct positive integers candidates and a target, return all combinations summing to target. The same number may be reused.

Example: candidates = [2,3,6,7], target = 7 → [[2,2,3],[7]]

🧭 From reading the problem to the solution

1. Break it down: combinations again, but a number can be reused. The difference is what start index you pass on recursion.
2. Key insight: ① since reuse is allowed, recurse with i (not i+1) so the same number can be picked again; ② still start from start (no going back) to avoid [2,3] vs [3,2]; ③ prune: return on remain < 0.
3. Optimum: backtracking with target as a decreasing remain.

def combinationSum(candidates, target):
    res = []
    def backtrack(start, path, remain):
        if remain == 0:
            res.append(path[:]); return
        if remain < 0:                          # prune
            return
        for i in range(start, len(candidates)):
            path.append(candidates[i])
            backtrack(i, path, remain - candidates[i])   # i: reusable
            path.pop()
    backtrack(0, [], target)
    return res

void backtrack(vector<int>& c, int start, int remain, vector<int>& path, vector<vector<int>>& res) {
    if (remain == 0) { res.push_back(path); return; }
    if (remain < 0) return;                      // prune
    for (int i = start; i < (int)c.size(); i++) {
        path.push_back(c[i]);
        backtrack(c, i, remain - c[i], path, res);   // i: reusable
        path.pop_back();
    }
}

• Complexity: exponential in the number of solutions; O(target / min) recursion depth.
• Pitfall: ① reusable → pass i; not reusable → pass i+1 (the dividing line for combination problems); ② still use a start index to avoid order duplicates; ③ LC 40 (each used once + duplicate values) needs sorting + "same-level dedup."

③ LC 46 — Permutations

📋 Problem: Given an array nums of distinct integers, return all possible permutations.

Example: [1,2,3] → 6 permutations

🧭 From reading the problem to the solution

1. Break it down: permutations care about order ([1,2] ≠ [2,1]), so you can't use a start index — any position can hold any "not-yet-used" number.
2. Key insight: use a used boolean array to mark which numbers are in the current path; each level scans all numbers, skipping used ones. Collect only at leaves (full path).
3. Optimum: backtracking + a used array.

def permute(nums):
    res = []
    def backtrack(path, used):
        if len(path) == len(nums):              # leaf: collect
            res.append(path[:]); return
        for i in range(len(nums)):
            if used[i]:                         # skip used
                continue
            used[i] = True; path.append(nums[i])
            backtrack(path, used)
            path.pop(); used[i] = False         # undo both
    backtrack([], [False] * len(nums))
    return res

void backtrack(vector<int>& nums, vector<int>& path, vector<bool>& used, vector<vector<int>>& res) {
    if (path.size() == nums.size()) { res.push_back(path); return; }
    for (int i = 0; i < (int)nums.size(); i++) {
        if (used[i]) continue;
        used[i] = true; path.push_back(nums[i]);
        backtrack(nums, path, used, res);
        path.pop_back(); used[i] = false;       // undo both
    }
}

• Complexity: O(n · n!) time, O(n) space.
• Pitfall: ① permutations use no start index (every position is open) — use a used array; ② on undo, restore both path.pop() and used[i]=False; ③ LC 47 (with duplicates) needs sorting + "skip same value at the same level if the previous wasn't used."

④ LC 79 — Word Search

📋 Problem: Given a character grid board and a string word, return whether word can be formed from adjacent (4-directional) cells, with no cell reused.

Example: word = "ABCCED" → true

🧭 From reading the problem to the solution

1. Break it down: "walk along adjacent cells to spell a string" — backtracking (DFS) on a grid, each cell extending in four directions.
2. Key insight: DFS from every cell as a start; when matching the i-th char, look in four directions for the i+1-th. Temporarily mark visited cells (no reuse), restore on backtrack.
3. Optimum: launch DFS per cell, matching the word char by char.

def exist(board, word):
    rows, cols = len(board), len(board[0])
    def dfs(r, c, i):
        if i == len(word):                      # matched all
            return True
        if (r < 0 or r >= rows or c < 0 or c >= cols
                or board[r][c] != word[i]):
            return False
        board[r][c] = '#'                       # mark visited
        found = (dfs(r+1, c, i+1) or dfs(r-1, c, i+1) or
                 dfs(r, c+1, i+1) or dfs(r, c-1, i+1))
        board[r][c] = word[i]                   # restore
        return found
    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True
    return False

bool dfs(vector<vector<char>>& board, string& word, int r, int c, int i) {
    if (i == (int)word.size()) return true;
    int rows = board.size(), cols = board[0].size();
    if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] != word[i]) return false;
    char tmp = board[r][c];
    board[r][c] = '#';                          // mark visited
    bool found = dfs(board, word, r+1, c, i+1) || dfs(board, word, r-1, c, i+1)
              || dfs(board, word, r, c+1, i+1) || dfs(board, word, r, c-1, i+1);
    board[r][c] = tmp;                          // restore
    return found;
}
bool exist(vector<vector<char>>& board, string word) {
    for (int r = 0; r < (int)board.size(); r++)
        for (int c = 0; c < (int)board[0].size(); c++)
            if (dfs(board, word, r, c, 0)) return true;
    return false;
}

• Complexity: O(m·n·4^L) time (L = word length), O(L) recursion space.
• Pitfall: ① mark visited cells (e.g. set to #) and restore after exploring — that's backtracking's "undo"; ② put bounds and char-mismatch checks at the top of DFS; ③ mutate the board instead of a separate visited array to save space (remember to restore).

⑤ LC 51 — N-Queens

📋 Problem: Place n queens on an n×n board so no two share a row, column, or diagonal; return all solutions.

Example: n = 4 → 2 solutions

🧭 From reading the problem to the solution

1. Break it down: place queens row by row (exactly one per row), deciding which column for each row. A classic "constrained backtracking."
2. Key insight (O(1) conflict check): keep three sets for occupied columns, main diagonals (r−c), and anti-diagonals (r+c) — O(1) conflict check before placing, pruning illegal branches. Same diagonal ⟺ same r−c (main) or same r+c (anti).
3. Optimum: row-by-row backtracking with three pruning sets.

def solveNQueens(n):
    res = []
    cols, diag1, diag2 = set(), set(), set()    # column, r-c, r+c
    board = [['.'] * n for _ in range(n)]
    def backtrack(r):
        if r == n:
            res.append([''.join(row) for row in board]); return
        for c in range(n):
            if c in cols or (r - c) in diag1 or (r + c) in diag2:
                continue                        # prune conflicts
            cols.add(c); diag1.add(r - c); diag2.add(r + c)
            board[r][c] = 'Q'
            backtrack(r + 1)
            board[r][c] = '.'                   # undo all
            cols.remove(c); diag1.remove(r - c); diag2.remove(r + c)
    backtrack(0)
    return res

int N;
vector<vector<string>> res;
vector<bool> cols, d1, d2;                       // d1: r-c+N-1, d2: r+c
vector<string> board;
void backtrack(int r) {
    if (r == N) { res.push_back(board); return; }
    for (int c = 0; c < N; c++) {
        if (cols[c] || d1[r - c + N - 1] || d2[r + c]) continue;   // prune
        cols[c] = d1[r - c + N - 1] = d2[r + c] = true;
        board[r][c] = 'Q';
        backtrack(r + 1);
        board[r][c] = '.';                                          // undo
        cols[c] = d1[r - c + N - 1] = d2[r + c] = false;
    }
}
vector<vector<string>> solveNQueens(int n) {
    N = n; res.clear();
    cols.assign(n, false); d1.assign(2*n, false); d2.assign(2*n, false);
    board.assign(n, string(n, '.'));
    backtrack(0);
    return res;
}

• Complexity: ~O(n!) time (far below nⁿ after pruning), O(n) space.
• Pitfall: ① place row by row (auto-guarantees distinct rows) so you only check columns and the two diagonals; ② identify diagonals by r−c (main) and r+c (anti); in C++ add N−1 to r−c to avoid a negative index; ③ on undo, restore all three sets + the board.

One Table to Remember It All

Pattern-Recognition Cheats

• "all subsets / power set" → start index, collect at every node.
• "combinations, make a target" → start index; reuse → pass i, no reuse → pass i+1.
• "all permutations, order matters" → used array, no start index.
• "board / grid spelling out a result" → grid DFS backtracking, mark visited then restore.
• "place N things with mutual constraints" → place level by level + O(1) pruning sets.

The essence of backtracking is one line: choose → recurse → un-choose — and the interview key is nailing "how the choice space is defined (start index? used array?)" and "how to prune." Weld the template; the rest is parameter swaps.