Backtracking

Back to DSA & Algorithms/00 - Roadmap Overview

What is Backtracking?

Backtracking = systematically try all possibilities, but abandon a path as soon as you know it can't lead to a valid solution. It's DFS with pruning.

The Mental Model

You're in a maze. At each fork, you pick a direction. If you hit a dead end, you backtrack to the last fork and try a different direction. You don't restart from the beginning — you undo just the last choice.

Decision tree for choosing from [1, 2, 3]:

         []
       / | \
     [1] [2] [3]        ← first choice
     /|   |   |\
  [1,2][1,3] ...        ← second choice
   |
  [1,2,3]               ← third choice → SOLUTION

The Universal Template

java
void backtrack(State state, List<Choice> choices) {
    // Base case: found a solution
    if (isComplete(state)) {
        result.add(new ArrayList<>(state));  // MUST copy — state mutates!
        return;
    }

    for (Choice choice : choices) {
        if (isValid(choice, state)) {        // Pruning
            state.add(choice);               // MAKE the choice
            backtrack(nextState);             // EXPLORE further
            state.remove(state.size() - 1);  // UNDO the choice (backtrack)
        }
    }
}

The Three Steps: Choose → Explore → Unchoose

Every backtracking problem follows this rhythm:

Choose: Pick an option from available choices
Explore: Recurse with that choice made
Unchoose: Undo the choice, try the next option

Time Complexity

Backtracking is inherently exponential:

Subsets: O(2^n) — each element is included or excluded
Permutations: O(n!) — n choices for first, n-1 for second, ...
Combinations: O(C(n,k)) — binomial coefficient

You can't avoid exponential time for these problems. Pruning reduces the constant factor but not the Big-O.

Pattern 1: Subsets (Include or Exclude Each Element)

What it is

Generate all possible subsets (power set). For n elements, there are 2^n subsets.

The Decision at Each Element

For each element, you have two choices: include it or skip it.

Elements: [1, 2, 3]

                    []
              /          \
           [1]            []         ← include 1 or not?
          /    \        /    \
       [1,2]  [1]    [2]    []      ← include 2 or not?
       / \    / \    / \    / \
   [1,2,3][1,2][1,3][1] [2,3][2] [3] []  ← include 3 or not?

Result: [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]

Step-by-Step

java
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> path, List<List<Integer>> result) {
    // Every node in the decision tree is a valid subset
    result.add(new ArrayList<>(path));  // Copy! path will change

    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);                // Choose
        backtrack(nums, i + 1, path, result);  // Explore (i+1: don't reuse elements)
        path.remove(path.size() - 1);     // Unchoose
    }
}

// Why start from i+1?
// To avoid duplicates: [1,2] and [2,1] are the same subset.
// By always picking from later indices, we enforce an order.

// Walkthrough: nums = [1, 2, 3]
// backtrack(0, []):
//   result.add([])  → result = 
//   i=0: path=[1] → backtrack(1, [1])
//     result.add([1]) → result = [[], [1]]
//     i=1: path=[1,2] → backtrack(2, [1,2])
//       result.add([1,2])
//       i=2: path=[1,2,3] → backtrack(3, [1,2,3])
//         result.add([1,2,3])
//       path.remove(last) → [1,2]
//     path.remove(last) → [1]
//     i=2: path=[1,3] → backtrack(3, [1,3])
//       result.add([1,3])
//     path.remove(last) → [1]
//   path.remove(last) → []
//   i=1: path=[2] → ... (continues)

Subsets with Duplicates

java
// Input: [1, 2, 2]
// Without handling duplicates: [[], [1], [1,2], [1,2,2], [1,2], [2], [2,2], [2]]
//                                              ^^^ duplicate [1,2]    ^^^ duplicate [2]

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

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

    for (int i = start; i < nums.length; i++) {
        // Skip duplicates: if this element equals the previous one
        // AND we're not at the start of this level
        if (i > start && nums[i] == nums[i - 1]) {
            continue;
        }

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

// The key line: if (i > start && nums[i] == nums[i - 1]) continue;
// "start" is the beginning of THIS level of choices.
// If i > start, it means we're trying a different element at the same position.
// If it's the same value as the previous one at this position, skip it.

Problems

78. Subsets - Medium
90. Subsets II - Medium

Pattern 2: Permutations (All Orderings)

What it is

Generate all possible orderings. For n elements, there are n! permutations.

The Difference from Subsets

Subsets: Choose which elements to include (order doesn't matter)
Permutations: Use all elements, choose the ORDER

java
public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> remaining = new ArrayList<>();
    for (int num : nums) remaining.add(num);
    backtrack(new ArrayList<>(), remaining, result);
    return result;
}

private void backtrack(List<Integer> path, List<Integer> remaining, List<List<Integer>> result) {
    if (remaining.isEmpty()) {           // Used all elements
        result.add(new ArrayList<>(path));
        return;
    }

    for (int i = 0; i < remaining.size(); i++) {
        path.add(remaining.get(i));                          // Choose
        int removed = remaining.remove(i);                   // Remove from remaining
        backtrack(path, remaining, result);                  // Explore
        remaining.add(i, removed);                           // Restore remaining
        path.remove(path.size() - 1);                        // Unchoose
    }
}

// Why remove from remaining?
// Remove the chosen element from available choices.
// We must use every element exactly once.
//
// Alternative (faster): swap-based
public List<List<Integer>> permuteSwap(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrackSwap(nums, 0, result);
    return result;
}

private void backtrackSwap(int[] nums, int start, List<List<Integer>> result) {
    if (start == nums.length) {
        List<Integer> snapshot = new ArrayList<>();
        for (int num : nums) snapshot.add(num);
        result.add(snapshot);
        return;
    }

    for (int i = start; i < nums.length; i++) {
        swap(nums, start, i);             // Swap (choose)
        backtrackSwap(nums, start + 1, result);  // Explore
        swap(nums, start, i);             // Swap back (unchoose)
    }
}

private void swap(int[] nums, int a, int b) {
    int temp = nums[a];
    nums[a] = nums[b];
    nums[b] = temp;
}

Permutations with Duplicates

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

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

    for (int i = 0; i < nums.length; i++) {
        if (used[i]) {
            continue;
        }
        // Skip duplicate: same value as previous, and previous wasn't used
        if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
            continue;
        }

        used[i] = true;
        path.add(nums[i]);
        backtrack(nums, path, used, result);
        path.remove(path.size() - 1);
        used[i] = false;
    }
}

Problems

Pattern 3: Combinations (Choose K from N)

What it is

Choose K elements from N (order doesn't matter). Like subsets, but all results must have exactly K elements.

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

private void backtrack(int n, int k, int start, List<Integer> path, List<List<Integer>> result) {
    if (path.size() == k) {
        result.add(new ArrayList<>(path));
        return;
    }

    // Pruning: stop early if not enough elements remaining
    int remainingNeeded = k - path.size();
    for (int i = start; i <= n - remainingNeeded + 1; i++) {
        path.add(i);
        backtrack(n, k, i + 1, path, result);
        path.remove(path.size() - 1);
    }
}

// The pruning: n - remainingNeeded + 1
// If we need 3 more elements and only 2 remain, stop early.
// This dramatically reduces exploration.

Combination Sum (Elements Can Be Reused)

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

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

    for (int i = start; i < candidates.length; i++) {
        path.add(candidates[i]);
        backtrack(candidates, i, path, remaining - candidates[i], result);  // i, not i+1 (reuse allowed!)
        path.remove(path.size() - 1);
    }
}

// Notice: backtrack(candidates, i, ...) not backtrack(candidates, i+1, ...)
// This allows using the same element multiple times.
// [2, 3, 6, 7], target=7 → [2,2,3] and [7]

Combination Sum II (No Reuse, Skip Duplicates)

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

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

    for (int i = start; i < candidates.length; i++) {
        if (candidates[i] > remaining) {
            break;  // Sorted: all future elements are too large
        }

        if (i > start && candidates[i] == candidates[i - 1]) {
            continue;  // Skip duplicates at this level
        }

        path.add(candidates[i]);
        backtrack(candidates, i + 1, path, remaining - candidates[i], result);  // i+1: no reuse
        path.remove(path.size() - 1);
    }
}

Problems

Pattern 4: Grid / Board Search

What it is

Search for a pattern on a 2D grid using DFS with backtracking (mark cells visited, unmark on backtrack).

java
public boolean exist(char[][] board, String word) {
    int rows = board.length, cols = board[0].length;

    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (backtrack(board, word, r, c, 0)) {
                return true;
            }
        }
    }
    return false;
}

private boolean backtrack(char[][] board, String word, int r, int c, int idx) {
    // Found the complete word
    if (idx == word.length()) {
        return true;
    }

    // Out of bounds, wrong character, or already visited
    if (r < 0 || r >= board.length || c < 0 || c >= board[0].length ||
        board[r][c] != word.charAt(idx)) {
        return false;
    }

    // Choose: mark as visited
    char temp = board[r][c];
    board[r][c] = '#';

    // Explore: try all 4 directions
    boolean found = backtrack(board, word, r + 1, c, idx + 1) ||
                    backtrack(board, word, r - 1, c, idx + 1) ||
                    backtrack(board, word, r, c + 1, idx + 1) ||
                    backtrack(board, word, r, c - 1, idx + 1);

    // Unchoose: restore the cell
    board[r][c] = temp;

    return found;
}

N-Queens

java
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, '.');
    Set<Integer> cols = new HashSet<>();
    Set<Integer> diag1 = new HashSet<>();  // row - col (top-left to bottom-right diagonals)
    Set<Integer> diag2 = new HashSet<>();  // row + col (top-right to bottom-left diagonals)
    backtrack(board, 0, cols, diag1, diag2, result);
    return result;
}

private void backtrack(char[][] board, int row, Set<Integer> cols,
                       Set<Integer> diag1, Set<Integer> diag2, List<List<String>> result) {
    int n = board.length;
    if (row == n) {
        List<String> snapshot = new ArrayList<>();
        for (char[] r : board) snapshot.add(new String(r));
        result.add(snapshot);
        return;
    }

    for (int col = 0; col < n; col++) {
        if (cols.contains(col) || diag1.contains(row - col) || diag2.contains(row + col)) {
            continue;  // Pruning: position under attack
        }

        board[row][col] = 'Q';
        cols.add(col);
        diag1.add(row - col);
        diag2.add(row + col);

        backtrack(board, row + 1, cols, diag1, diag2, result);

        board[row][col] = '.';
        cols.remove(col);
        diag1.remove(row - col);
        diag2.remove(row + col);
    }
}

// The diagonal trick:
// Cells on the same ↘ diagonal have the same (row - col)
// Cells on the same ↗ diagonal have the same (row + col)

Problems

Pattern 5: String Partitioning / Generation

java
// Generate all valid parentheses combinations
public List<String> generateParenthesis(int n) {
    List<String> result = new ArrayList<>();
    backtrack(new StringBuilder(), 0, 0, n, result);
    return result;
}

private void backtrack(StringBuilder path, int openCount, int closeCount, int n, List<String> result) {
    if (path.length() == 2 * n) {
        result.add(path.toString());
        return;
    }

    if (openCount < n) {
        path.append('(');
        backtrack(path, openCount + 1, closeCount, n, result);
        path.deleteCharAt(path.length() - 1);
    }

    if (closeCount < openCount) {  // Can only close if there's an open to match
        path.append(')');
        backtrack(path, openCount, closeCount + 1, n, result);
        path.deleteCharAt(path.length() - 1);
    }
}

Problems

131. Palindrome Partitioning - Medium
93. Restore IP Addresses - Medium
17. Letter Combinations of a Phone Number - Medium
22. Generate Parentheses - Medium

The Comparison Table (Know This!)

Problem Type	Order matters?	Reuse?	Template Key Difference
Subsets	No	No	Start from `i`, recurse with `i+1`
Permutations	Yes	No	Try all remaining elements
Combinations	No	No	Start from `i`, stop at K elements
Combination Sum	No	Yes	Start from `i`, recurse with `i` (not `i+1`)

Things You MUST Be Aware Of

1. ALWAYS Copy the Path

java
result.add(new ArrayList<>(path));    // Copy with new ArrayList<>(path)
// NOT: result.add(path);  ← This stores a REFERENCE. 
// When path changes later, all stored results change too!

2. Handling Duplicates

java
// Step 1: Sort the input
// Step 2: Skip if same as previous at the same decision level
if (i > start && nums[i] == nums[i - 1]) {
    continue;
}

3. Pruning = Performance

java
// Without pruning: explore entire tree (slow)
// With pruning: skip branches that can't lead to solutions (fast)

// Common pruning strategies:
// - Sum exceeds target → stop
// - Not enough elements remaining → stop
// - Position under attack (N-Queens) → skip
// - Sorted + current element too large → break (not continue!)

4. `continue` vs `break`

java
// continue: skip this element, try the next one
// break: stop trying all remaining elements at this level

// Use break when the input is sorted and you know all future elements
// will also fail (e.g., sum already exceeds target)

Decision Guide

"Generate all subsets"
  └── Subset pattern (include/exclude each element)

"Generate all orderings"
  └── Permutation pattern (try all remaining)

"Choose K elements"
  └── Combination pattern (subsets of fixed size)

"Find combinations that sum to target"
  └── Combination Sum (can reuse → i, can't reuse → i+1)

"Search for pattern in a grid"
  └── Grid backtracking (mark visited, try 4 directions)

"Place items without conflicts"
  └── Constraint satisfaction (like N-Queens)

"Split string into valid parts"
  └── String partitioning (try all split points)

Backtracking

What is Backtracking?

The Mental Model

The Universal Template

The Three Steps: Choose → Explore → Unchoose

Time Complexity

Pattern 1: Subsets (Include or Exclude Each Element)

What it is

The Decision at Each Element

Step-by-Step

Subsets with Duplicates

Problems

Pattern 2: Permutations (All Orderings)

What it is

The Difference from Subsets

Permutations with Duplicates

Problems

Pattern 3: Combinations (Choose K from N)

What it is

Combination Sum (Elements Can Be Reused)

Combination Sum II (No Reuse, Skip Duplicates)

Problems

Pattern 4: Grid / Board Search

What it is

N-Queens

Problems

Pattern 5: String Partitioning / Generation

Problems

The Comparison Table (Know This!)

Things You MUST Be Aware Of

1. ALWAYS Copy the Path

2. Handling Duplicates

3. Pruning = Performance

4. continue vs break

Decision Guide

4. `continue` vs `break`