Backtracking Pattern

Overview

Systematically explore all possible solutions by building candidates incrementally and abandoning ("backtracking") when a candidate cannot lead to a valid solution.

When to Use

• Generate all combinations/permutations
• Solve constraint satisfaction (Sudoku, N-Queens)
• Path finding with constraints
• Subset/partition problems
• Decision tree exploration
• "Find all possible..." questions

Template Code

General Backtracking Template

public void backtrack(State state, List<Result> results) {
    if (isValidSolution(state)) {
        results.add(copy(state));
        return;
    }

    for (Choice choice : getChoices(state)) {
        if (isValid(choice)) {
            // Make choice
            applyChoice(state, choice);

            // Explore
            backtrack(state, results);

            // Undo choice (backtrack)
            undoChoice(state, choice);
        }
    }
}

Subsets (Power Set)

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

private void backtrack(int[] nums, int start, List<Integer> current,
                       List<List<Integer>> result) {
    result.add(new ArrayList<>(current));  // Every path is valid

    for (int i = start; i < nums.length; i++) {
        current.add(nums[i]);
        backtrack(nums, i + 1, current, result);
        current.remove(current.size() - 1);
    }
}

Subsets II (With Duplicates)

public List<List<Integer>> subsetsWithDup(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(nums);  // Sort to handle duplicates
    backtrack(nums, 0, new ArrayList<>(), result);
    return result;
}

private void backtrack(int[] nums, int start, List<Integer> current,
                       List<List<Integer>> result) {
    result.add(new ArrayList<>(current));

    for (int i = start; i < nums.length; i++) {
        // Skip duplicates at same level
        if (i > start && nums[i] == nums[i - 1]) continue;

        current.add(nums[i]);
        backtrack(nums, i + 1, current, result);
        current.remove(current.size() - 1);
    }
}

Permutations

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

private void backtrack(int[] nums, boolean[] used, List<Integer> current,
                       List<List<Integer>> result) {
    if (current.size() == nums.length) {
        result.add(new ArrayList<>(current));
        return;
    }

    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;

        used[i] = true;
        current.add(nums[i]);

        backtrack(nums, used, current, result);

        current.remove(current.size() - 1);
        used[i] = false;
    }
}

Permutations II (With Duplicates)

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

private void backtrack(int[] nums, boolean[] used, List<Integer> current,
                       List<List<Integer>> result) {
    if (current.size() == nums.length) {
        result.add(new ArrayList<>(current));
        return;
    }

    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;

        // Skip duplicates: only use if previous duplicate was used
        if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;

        used[i] = true;
        current.add(nums[i]);

        backtrack(nums, used, current, result);

        current.remove(current.size() - 1);
        used[i] = false;
    }
}

Combination Sum

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

private void backtrack(int[] candidates, int remaining, int start,
                       List<Integer> current, List<List<Integer>> result) {
    if (remaining == 0) {
        result.add(new ArrayList<>(current));
        return;
    }

    for (int i = start; i < candidates.length; i++) {
        if (candidates[i] > remaining) continue;

        current.add(candidates[i]);
        backtrack(candidates, remaining - candidates[i], i, current, result);
        current.remove(current.size() - 1);
    }
}

Combination Sum II (Each Number Once)

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

private void backtrack(int[] candidates, int remaining, int start,
                       List<Integer> current, List<List<Integer>> result) {
    if (remaining == 0) {
        result.add(new ArrayList<>(current));
        return;
    }

    for (int i = start; i < candidates.length; i++) {
        if (candidates[i] > remaining) break;
        if (i > start && candidates[i] == candidates[i - 1]) continue;

        current.add(candidates[i]);
        backtrack(candidates, remaining - candidates[i], i + 1, current, result);
        current.remove(current.size() - 1);
    }
}

N-Queens

public 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(board, 0, result);
    return result;
}

private void backtrack(char[][] board, int row, List<List<String>> result) {
    if (row == board.length) {
        result.add(construct(board));
        return;
    }

    for (int col = 0; col < board.length; col++) {
        if (isValid(board, row, col)) {
            board[row][col] = 'Q';
            backtrack(board, row + 1, result);
            board[row][col] = '.';
        }
    }
}

private boolean isValid(char[][] board, int row, int col) {
    int n = board.length;

    // Check column above
    for (int i = 0; i < row; i++) {
        if (board[i][col] == 'Q') return false;
    }

    // Check upper-left diagonal
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 'Q') return false;
    }

    // Check upper-right diagonal
    for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        if (board[i][j] == 'Q') return false;
    }

    return true;
}

private List<String> construct(char[][] board) {
    List<String> result = new ArrayList<>();
    for (char[] row : board) {
        result.add(new String(row));
    }
    return result;
}

Word Search

public boolean exist(char[][] board, String word) {
    int m = board.length, n = board[0].length;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (backtrack(board, word, i, j, 0)) {
                return true;
            }
        }
    }

    return false;
}

private boolean backtrack(char[][] board, String word, int i, int j, int index) {
    if (index == word.length()) return true;

    if (i < 0 || i >= board.length || j < 0 || j >= board[0].length ||
        board[i][j] != word.charAt(index)) {
        return false;
    }

    char temp = board[i][j];
    board[i][j] = '#';  // Mark visited

    boolean found = backtrack(board, word, i + 1, j, index + 1) ||
                   backtrack(board, word, i - 1, j, index + 1) ||
                   backtrack(board, word, i, j + 1, index + 1) ||
                   backtrack(board, word, i, j - 1, index + 1);

    board[i][j] = temp;  // Restore
    return found;
}

Palindrome Partitioning

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

private void backtrack(String s, int start, List<String> current,
                       List<List<String>> result) {
    if (start == s.length()) {
        result.add(new ArrayList<>(current));
        return;
    }

    for (int end = start + 1; end <= s.length(); end++) {
        String substr = s.substring(start, end);
        if (isPalindrome(substr)) {
            current.add(substr);
            backtrack(s, end, current, result);
            current.remove(current.size() - 1);
        }
    }
}

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

Time & Space Complexity

Problem	Time	Space
Subsets	O(2^n × n)	O(n)
Permutations	O(n! × n)	O(n)
Combinations	O(C(n,k) × k)	O(k)
N-Queens	O(n!)	O(n²)
Word Search	O(m × n × 4^L)	O(L)

Common Interview Questions

1. Subsets - All subsets of array
2. Subsets II - With duplicates
3. Permutations - All orderings
4. Permutations II - With duplicates
5. Combinations - Choose k from n
6. Combination Sum - Numbers sum to target (reuse)
7. Combination Sum II - Each number once
8. N-Queens - Place n queens
9. Word Search - Find word in grid
10. Palindrome Partitioning - All palindrome partitions
11. Letter Combinations of Phone - Phone keypad
12. Generate Parentheses - Valid parentheses strings
13. Sudoku Solver - Fill valid sudoku
14. Restore IP Addresses - Valid IP from digits

Tips & Tricks

• Sort input to handle duplicates elegantly
• Skip duplicates at same recursion level with i > start && nums[i] == nums[i-1]
• For permutations, track used[] array
• For combinations/subsets, use start index to avoid revisiting
• Make deep copies when adding to result
• Consider early termination (pruning) for optimization
• Modify input in-place to mark visited (restore after)