Backtracking

Backtracking explores all possible solutions by incrementally building candidates and abandoning a path the moment it violates constraints.

• Replaces brute-force enumeration with structured pruning — only explores branches that can still lead to a valid solution
• Three modes: subset/combination (start index prevents revisiting earlier elements), permutation (visited array, try all positions every level), constraint-based (validity check before placing)
• Reach for it when you need all valid arrangements, subsets, or paths, and the problem says "return all" or "find all"

Quick Revision - Must Do Problems

If short on time, solve only these. They cover ~90% of backtracking patterns.

Practice Tips

How to Identify a Backtracking Problem

• Problem says "return all combinations", "all permutations", "all subsets", "all valid arrangements"
• You need to explore a search space and prune invalid paths early
• The answer is a collection of complete paths, not a single optimal value
• Grid problem asks to find a word or path (not shortest — that's BFS)

Backtracking vs. Other Techniques

Interview Approach

1. Identify which mode: subset (start index, add at every node), combination (start index, add at base case), permutation (visited array), or constraint-based
2. Write the base case first: when do you add to results and return?
3. Write the loop: what are the choices at this level?
4. Choose: add to path
5. Recurse with updated state
6. Unchoose: remove from path (backtrack)

4 Main Patterns

Pattern 1: Subset / Power Set

Copy// Add result at every node (before the loop) — captures empty set and all partial sets
private void backtrack(List<List<Integer>> result, List<Integer> path, int[] nums, int start) {
    result.add(new ArrayList<>(path));          // add at every node
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);
        backtrack(result, path, nums, i + 1);   // i+1 = no revisit
        path.remove(path.size() - 1);
    }
}

Pattern 2: Combination (Target Sum or Fixed Size)

Copy// Add result only at base case — either size==k or remain==0
private void backtrack(..., int remain, int start) {
    if (remain == 0) {
        result.add(new ArrayList<>(path)); return;
    }
    for (int i = start; i < candidates.length; i++) {
        path.add(candidates[i]);
        backtrack(..., remain - candidates[i], i);     // i = reuse allowed
     // backtrack(..., remain - candidates[i], i + 1); // i+1 = no reuse
        path.remove(path.size() - 1);
    }
}

Pattern 3: Permutation

Copy// No start index — try every position each level; visited[] prevents reuse
private void backtrack(List<List<Integer>> result, List<Integer> path, int[] nums, boolean[] used) {
    if (path.size() == nums.length) {
        result.add(new ArrayList<>(path)); return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) {
            continue;
        }
        used[i] = true;
        path.add(nums[i]);
        backtrack(result, path, nums, used);
        path.remove(path.size() - 1);
        used[i] = false;
    }
}

Pattern 4: Constraint-Based Construction

Copy// No start index, no input array — build char by char with validity constraints
private void backtrack(List<String> result, StringBuilder path, int open, int close, int n) {
    if (path.length() == 2 * n) {
        result.add(path.toString()); return;
    }
    if (open < n) {
        path.append('('); backtrack(..., open+1, close, n); path.deleteCharAt(path.length()-1);
    }
    if (close < open) {
        path.append(')'); backtrack(..., open, close+1, n); path.deleteCharAt(path.length()-1);
    }
}

General Templates

Duplicate Handling (Subsets / Combos with Duplicates)

Copy// Sort first, then skip same value at same recursion level
Arrays.sort(nums);
// Inside the loop:
if (i > start && nums[i] == nums[i - 1]) {
    continue;  // i > start, NOT i > 0
}

Duplicate Handling (Permutations with Duplicates)

Copy// Sort first, then skip if same value as previous AND previous not currently in use
Arrays.sort(nums);
// Inside the loop:
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
    continue;
}

Grid Backtracking (Mark + Restore)

Copy// Mark visited in-place; restore after recursion (backtrack step)
char tmp = board[r][c];
board[r][c] = '#';           // mark visited
// ... recurse in 4 directions ...
board[r][c] = tmp;           // restore (the backtrack step)

Problem 1: Subsets ⭐ MUST DO

Given an array of unique integers, return all possible subsets (the power set).

Example:

CopyInput:  [1, 2, 3]
Output: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

Key Insight:

• Add the current path to results before the loop, not only at leaves. This captures the empty set (first call, empty path) and every partial subset as we recurse. Every node in the recursion tree is a valid subset.

Solution:

Copypublic List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(result, new ArrayList<>(), nums, 0);
    return result;
}

private void backtrack(List<List<Integer>> result, List<Integer> path, int[] nums, int start) {
    result.add(new ArrayList<>(path));              // add at every node
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);
        backtrack(result, path, nums, i + 1);       // i+1: don't revisit earlier elements
        path.remove(path.size() - 1);
    }
}

Complexity:

Problem 2: Letter Combinations of a Phone Number

Given a string of digits 2–9, return all possible letter combinations the number could represent (like a phone keypad).

Example:

CopyInput:  "23"  →  ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Input:  ""    →  []

Key Insight:

• Treat each digit as one level of recursion. The letters mapped to that digit are the choices at that level. Advance by index each level — no start index needed since each digit occupies a fixed position.

Solution:

Copyprivate static final String[] KEYS = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};

public List<String> letterCombinations(String digits) {
    List<String> result = new ArrayList<>();
    if (digits == null || digits.length() == 0) {
        return result;
    }
    backtrack(result, new StringBuilder(), digits, 0);
    return result;
}

private void backtrack(List<String> result, StringBuilder path, String digits, int index) {
    if (index == digits.length()) {
        result.add(path.toString()); return;
    }
    for (char c : KEYS[digits.charAt(index) - '0'].toCharArray()) {
        path.append(c);
        backtrack(result, path, digits, index + 1);
        path.deleteCharAt(path.length() - 1);
    }
}

Complexity:

Problem 3: Generate Parentheses ⭐ MUST DO

Given n pairs of parentheses, generate all combinations of well-formed parentheses.

Example:

CopyInput:  n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Key Insight:

• Two constraints define validity: add '(' only if open < n (haven't used all opens yet); add ')' only if close < open (can't close more than you've opened). Any path satisfying both constraints is guaranteed to produce a valid string — no need to validate at the end.

Solution:

Copypublic List<String> generateParenthesis(int n) {
    List<String> result = new ArrayList<>();
    backtrack(result, new StringBuilder(), 0, 0, n);
    return result;
}

private void backtrack(List<String> result, StringBuilder path, int open, int close, int n) {
    if (path.length() == 2 * n) {
        result.add(path.toString()); return;
    }
    if (open < n) {
        path.append('(');
        backtrack(result, path, open + 1, close, n);
        path.deleteCharAt(path.length() - 1);
    }
    if (close < open) {
        path.append(')');
        backtrack(result, path, open, close + 1, n);
        path.deleteCharAt(path.length() - 1);
    }
}

Complexity:

Problem 4: Combinations

Return all possible combinations of k numbers chosen from the range [1, n].

Example:

CopyInput:  n = 4, k = 2  →  [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Input:  n = 1, k = 1  →  [[1]]

Key Insight:

• Prune early: if fewer than k - path.size() numbers remain in the range, it's impossible to complete the combination. The loop only needs to go up to n - (k - path.size()) + 1.

Solution:

Copypublic List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(result, new ArrayList<>(), 1, n, k);
    return result;
}

private void backtrack(List<List<Integer>> result, List<Integer> path, int start, int n, int k) {
    if (path.size() == k) {
        result.add(new ArrayList<>(path)); return;
    }
    for (int i = start; i <= n - (k - path.size()) + 1; i++) {  // pruning upper bound
        path.add(i);
        backtrack(result, path, i + 1, n, k);
        path.remove(path.size() - 1);
    }
}

Complexity:

Problem 5: Subsets II

Given an integer array that may contain duplicates, return all possible subsets without duplicate subsets.

Example:

CopyInput:  [1, 2, 2]  →  [[], [1], [1,2], [1,2,2], [2], [2,2]]
Input:  [0]        →  [[], [0]]

Key Insight:

• Sort first so duplicates are adjacent. Skip a value in the loop if it equals the previous value at the same recursion level (i > start). This skips duplicate subsets without skipping duplicates across levels (which would lose valid multi-element subsets like [2,2]).

Solution:

Copypublic List<List<Integer>> subsetsWithDup(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(result, new ArrayList<>(), nums, 0);
    return result;
}

private void backtrack(List<List<Integer>> result, List<Integer> path, int[] nums, int start) {
    result.add(new ArrayList<>(path));
    for (int i = start; i < nums.length; i++) {
        if (i > start && nums[i] == nums[i - 1]) {
            continue; // skip duplicate at same level
        }
        path.add(nums[i]);
        backtrack(result, path, nums, i + 1);
        path.remove(path.size() - 1);
    }
}

Complexity:

Problem 6: Permutations ⭐ MUST DO

Given an array of distinct integers, return all possible permutations.

Example:

CopyInput:  [1, 2, 3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Key Insight:

• Unlike subset/combination backtracking, permutations have no start index — every level can use any unused element. A visited[] boolean array tracks which elements are currently in the path. At each level, loop over the entire array and skip already-used indices.

Solution:

Copypublic List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(result, new ArrayList<>(), nums, new boolean[nums.length]);
    return result;
}

private void backtrack(List<List<Integer>> result, List<Integer> path, int[] nums, boolean[] used) {
    if (path.size() == nums.length) {
        result.add(new ArrayList<>(path)); return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) {
            continue;
        }
        used[i] = true;
        path.add(nums[i]);
        backtrack(result, path, nums, used);
        path.remove(path.size() - 1);
        used[i] = false;
    }
}

Complexity:

Problem 7: Permutations II

Given a collection that may contain duplicates, return all unique permutations.

Example:

CopyInput:  [1, 1, 2]  →  [[1,1,2],[1,2,1],[2,1,1]]
Input:  [1, 2, 3]  →  [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Key Insight:

• Sort first. Skip element i if it equals element i-1 AND element i-1 is not currently used (!used[i-1]). This means: if the previous duplicate copy was not used in this path position, don't use this copy either — it would produce the same permutation.

Solution:

Copypublic List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(result, new ArrayList<>(), nums, new boolean[nums.length]);
    return result;
}

private void backtrack(List<List<Integer>> result, List<Integer> path, int[] nums, boolean[] used) {
    if (path.size() == nums.length) {
        result.add(new ArrayList<>(path)); return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) {
            continue;
        }
        if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
            continue; // skip dup perms
        }
        used[i] = true;
        path.add(nums[i]);
        backtrack(result, path, nums, used);
        path.remove(path.size() - 1);
        used[i] = false;
    }
}

Complexity:

Problem 8: Combination Sum ⭐ MUST DO

Given distinct candidates and a target, return all unique combinations that sum to target. The same number may be used unlimited times.

Example:

CopyInput:  candidates = [2,3,6,7],  target = 7  →  [[2,2,3],[7]]
Input:  candidates = [2,3,5],    target = 8  →  [[2,2,2,2],[2,3,3],[3,5]]

Key Insight:

• Pass i (not i+1) into the recursive call to allow reusing the same element. Sort candidates to enable early termination: if the current candidate exceeds the remaining target, all further candidates (which are larger) can be skipped.

Solution:

Copypublic List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(candidates);
    backtrack(result, new ArrayList<>(), candidates, target, 0);
    return result;
}

private void backtrack(List<List<Integer>> result, List<Integer> path,
                       int[] candidates, int remain, int start) {
    if (remain == 0) {
        result.add(new ArrayList<>(path)); return;
    }
    for (int i = start; i < candidates.length; i++) {
        if (candidates[i] > remain) {
            break;      // sorted: rest are also too big
        }
        path.add(candidates[i]);
        backtrack(result, path, candidates, remain - candidates[i], i); // i = reuse
        path.remove(path.size() - 1);
    }
}

Complexity:

Problem 9: Combination Sum II

Given candidates that may contain duplicates, return all unique combinations that sum to target. Each number may only be used once.

Example:

CopyInput:  candidates = [10,1,2,7,6,1,5],  target = 8  →  [[1,1,6],[1,2,5],[1,7],[2,6]]
Input:  candidates = [2,5,2,1,2],         target = 5  →  [[1,2,2],[5]]

Key Insight:

• Combination Sum I vs II: use i+1 (not i) so each element is used at most once. For duplicates, sort and skip candidates[i] == candidates[i-1] at the same level — same rule as Subsets II.

Solution:

Copypublic List<List<Integer>> combinationSum2(int[] candidates, int target) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(candidates);
    backtrack(result, new ArrayList<>(), candidates, target, 0);
    return result;
}

private void backtrack(List<List<Integer>> result, List<Integer> path,
                       int[] candidates, int remain, int start) {
    if (remain == 0) {
        result.add(new ArrayList<>(path)); return;
    }
    for (int i = start; i < candidates.length; i++) {
        if (i > start && candidates[i] == candidates[i - 1]) {
            continue; // skip dups
        }
        if (candidates[i] > remain) {
            break;
        }
        path.add(candidates[i]);
        backtrack(result, path, candidates, remain - candidates[i], i + 1); // i+1 = no reuse
        path.remove(path.size() - 1);
    }
}

Complexity:

Problem 10: Palindrome Partitioning

Partition a string such that every substring is a palindrome. Return all possible partitions.

Example:

CopyInput:  "aab"  →  [["a","a","b"], ["aa","b"]]
Input:  "a"    →  [["a"]]

Key Insight:

• At each position, try all possible end positions. Only recurse if the current substring is a palindrome — this is the pruning condition. When start reaches the end of the string, the entire string has been partitioned into palindromes.

Solution:

Copypublic List<List<String>> partition(String s) {
    List<List<String>> result = new ArrayList<>();
    backtrack(result, new ArrayList<>(), s, 0);
    return result;
}

private void backtrack(List<List<String>> result, List<String> path, String s, int start) {
    if (start == s.length()) {
        result.add(new ArrayList<>(path)); return;
    }
    for (int end = start + 1; end <= s.length(); end++) {
        if (isPalindrome(s, start, end - 1)) {
            path.add(s.substring(start, end));
            backtrack(result, path, s, end);
            path.remove(path.size() - 1);
        }
    }
}

private boolean isPalindrome(String s, int left, int right) {
    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

Complexity:

Problem 11: Word Search ⭐ MUST DO [B75-79]

Given a grid of characters and a word, return true if the word exists in the grid. It must be constructed from sequentially adjacent cells (horizontal/vertical). Each cell may not be used more than once.

Example:

CopyBoard:         word = "ABCCED"  →  true
A B C E
S F C S        word = "SEE"     →  true
A D E E
               word = "ABCB"    →  false  (can't reuse B)

Key Insight:

• DFS from each cell that matches word[0]. Mark the current cell visited by overwriting with '#' so it won't be reused in the current path. After recursing into all 4 directions, restore the original character — this is the backtrack step. Without it, a failed search path would leave corrupted cells that block subsequent starting points.

Solution:

Copypublic boolean exist(char[][] board, String word) {
    for (int r = 0; r < board.length; r++) {
        for (int c = 0; c < board[0].length; c++)
    }
            if (dfs(board, word, r, c, 0)) {
                return true;
            }
    return false;
}

private boolean dfs(char[][] board, String word, int r, int c, int idx) {
    if (idx == word.length()) {
        return true;
    }
    if (r < 0 || r >= board.length || c < 0 || c >= board[0].length
            || board[r][c] != word.charAt(idx)) return false;
    char tmp = board[r][c];
    board[r][c] = '#';                          // mark visited
    boolean found = dfs(board, word, r+1, c, idx+1)
                 || dfs(board, word, r-1, c, idx+1)
                 || dfs(board, word, r, c+1, idx+1)
                 || dfs(board, word, r, c-1, idx+1);
    board[r][c] = tmp;                          // restore (backtrack)
    return found;
}

Complexity:

Problem 12: N-Queens ⭐ MUST DO

Place n queens on an n×n chessboard so no two queens attack each other. Return all distinct solutions.

Example:

CopyInput: n = 4
Output: [".Q..","...Q","Q...","..Q."]  and  ["..Q.","Q...","...Q",".Q.."]

Key Insight:

• Place one queen per row — this automatically ensures no two queens share a row. For each column in the current row, check three threats: same column above, top-left diagonal, top-right diagonal. Only recurse if the placement is safe. Backtrack by removing the queen and trying the next column.

Solution:

Copypublic List<List<String>> solveNQueens(int n) {
    List<List<String>> result = new ArrayList<>();
    char[][] board = new char[n][n];
    for (char[] row : board) {
        Arrays.fill(row, '.');
    }
    backtrack(result, board, 0);
    return result;
}

private void backtrack(List<List<String>> result, char[][] board, int row) {
    if (row == board.length) {
        List<String> solution = new ArrayList<>();
        for (char[] r : board) {
            solution.add(new String(r));
        }
        result.add(solution);
        return;
    }
    for (int col = 0; col < board.length; col++) {
        if (isValid(board, row, col)) {
            board[row][col] = 'Q';
            backtrack(result, board, row + 1);
            board[row][col] = '.';
        }
    }
}

private boolean isValid(char[][] board, int row, int col) {
    int n = board.length;
    for (int i = 0; i < row; i++) {
        if (board[i][col] == 'Q') return false;                 // same column
    }
    for (int i = row-1, j = col-1; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 'Q') return false;                   // top-left diagonal
    }
    for (int i = row-1, j = col+1; i >= 0 && j < n; i--, j++) {
        if (board[i][j] == 'Q') return false;                   // top-right diagonal
    }
    return true;
}

Complexity:

Quick Reference Table

When to Use Each Pattern

Subset / Power Set

• Need all subsets, combinations of any size
• Add to results before the loop (at every node), not just at leaves
• Use i + 1 in the recursive call to prevent revisiting earlier elements

Combination (Fixed Size or Target Sum)

• Need combinations of exactly k elements or combinations summing to a target
• Add to results only at the base case (size==k or remain==0)
• Reuse allowed: pass i; no reuse: pass i + 1; pruning: sort and break when candidate > remain

Permutation

• Need all orderings — every position can take any unused element
• No start index parameter; use a visited[] boolean array instead
• Loop from index 0 every level; skip used[i]

Constraint-Based Construction

• Build a solution character-by-character with validity constraints at each step
• No input array to iterate — generate choices based on current state (open/close counts, row/col)
• Only branch when the constraint allows it; no need to undo a failed attempt — just don't add

Common Mistakes to Avoid

General Backtracking Mistakes

1. Not copying the path — result.add(path) adds a reference, not a copy; always use result.add(new ArrayList<>(path)) or path.toString()
2. Missing the backtrack step — after every path.add(...) and recurse, there must be a matching path.remove(...) or path.deleteCharAt(...); forgetting it corrupts all subsequent paths

Subset / Combination Mistakes

3. Using i > 0 instead of i > start for duplicate skipping — i > 0 would incorrectly skip the first occurrence of a value in a sub-problem; always check i > start
4. Wrong start index for reuse — Combination Sum (reuse allowed) passes i; Combination Sum II (no reuse) passes i + 1; mixing these causes wrong results

Permutation Mistakes

5. Not resetting visited[i] — after backtracking, used[i] = false must be called; failing to reset it prevents that element from appearing in other permutation branches
6. Wrong condition for Permutations II — the skip condition is !used[i-1] (previous copy not in current path), not used[i-1]; reversing it produces too few results

Grid Backtracking Mistakes

7. Not restoring the cell — in Word Search, board[r][c] = tmp after recursion is the backtrack step; without it, cells marked '#' stay corrupted for subsequent start positions
8. Checking bounds after accessing the array — always check bounds before accessing board[r][c]; accessing out-of-bounds first causes ArrayIndexOutOfBoundsException