DSA Part 17: Backtracking & Constraint Search

                Mastery target: Level A recognition, progressing toward Level B implementation. You should be able to write the generic backtracking template from memory, apply it to permutations, subsets, combination sum, and N-Queens, and explain how forward checking and the MRV heuristic prune the search tree faster than brute-force recursion.
            

1. Introduction & Motivation

Some problems cannot be solved by a formula or a single greedy pass - they require searching a space of candidate solutions and rejecting the ones that violate a constraint. Backtracking is the disciplined way to run that search: build a candidate one decision at a time, check the constraint as early as possible, and undo the most recent decision the instant it fails. Done well, backtracking still explores an exponential space, but it prunes entire branches before they are fully built, which is the difference between an algorithm that finishes and one that never returns.

This lesson is the last of six that split apart a single overloaded guide to graphs, dynamic programming, greedy algorithms, and backtracking. Where greedy algorithms commit to one choice per step and never look back, backtracking keeps every option open and reverses course the moment a choice proves wrong. That reversal - make_choice, recurse, undo_choice - is the one idea this entire lesson builds on, from generating permutations to solving N-Queens with bitmask pruning.

2. Prerequisites

Backtracking is recursion plus one extra discipline: undo what you just did before trying the next option. If recursive call stacks, base cases, and tracing a call tree by hand are not yet comfortable, work through Part 2: Recursion Complete Guide first - everything below assumes you can reason about a recursive call tree without writing it out.

This lesson also assumes you can tell backtracking apart from the algorithm family it is most often confused with: greedy algorithms. Part 16: Greedy Proofs & Scheduling proves when committing to the locally best choice is safe and never needs to be undone. Backtracking is what you reach for when no such proof exists - when the only way to know a choice was wrong is to keep going and eventually fail.

3. The Backtracking Template

Backtracking is a systematic way to explore all possible solutions by building candidates incrementally and abandoning ("backtracking") candidates that fail to satisfy constraints.

Backtracking Template

def backtrack(candidate):
    if is_solution(candidate):
        output(candidate)
        return

    for choice in choices:
        if is_valid(choice):
            make_choice(choice)
            backtrack(candidate)
            undo_choice(choice)  # Backtrack

4. Permutations

Generate all possible orderings of a given set. At each position, try every unused element, recurse to fill the next position, then undo the choice (backtrack). The decision tree has $n!$ leaves (one per permutation). Key constraint: use a "used" boolean array to avoid placing the same element twice. For duplicates, sort first and skip adjacent identical unused elements to avoid duplicate permutations.

def permute(nums):
    """
    LeetCode 46: Permutations
    Generate all permutations
    Time: O(n! * n), Space: O(n)
    """
    result = []

    def backtrack(current, remaining):
        if not remaining:
            result.append(current[:])
            return

        for i in range(len(remaining)):
            # Make choice
            current.append(remaining[i])

            # Recurse with remaining elements
            backtrack(current, remaining[:i] + remaining[i+1:])

            # Undo choice
            current.pop()

    backtrack([], nums)
    return result

# Example
nums = [1, 2, 3]
print(f"Permutations of {nums}:")
for perm in permute(nums):
    print(f"  {perm}")

// LeetCode 46: Permutations
// Time: O(n! * n), Space: O(n)
#include <vector>

class Permutations {
public:
    static std::vector<std::vector<int>> permute(std::vector<int>& nums) {
        std::vector<std::vector<int>> result;
        std::vector<int> current;
        std::vector<bool> used(nums.size(), false);
        backtrack(nums, current, used, result);
        return result;
    }

private:
    static void backtrack(std::vector<int>& nums, std::vector<int>& current,
                          std::vector<bool>& used, std::vector<std::vector<int>>& result) {
        if (current.size() == nums.size()) {
            result.push_back(current);
            return;
        }

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

            current.push_back(nums[i]);
            used[i] = true;
            backtrack(nums, current, used, result);
            current.pop_back();
            used[i] = false;
        }
    }
};

// LeetCode 46: Permutations
// Time: O(n! * n), Space: O(n)
import java.util.*;

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

    private static void backtrack(int[] nums, List<Integer> current,
                                   boolean[] used, 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;

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

5. Subsets

Generate all $2^n$ subsets (the power set) of a given array. At each element, make a binary choice: include it or exclude it. The recursion tree branches two ways at each level, giving $2^n$ total subsets. Implementation uses an index $i$ to avoid revisiting earlier elements (since subset order doesn't matter). This is the foundation for many search problems — Subsets II (with duplicates) adds a skip condition for consecutive identical values.

def subsets(nums):
    """
    LeetCode 78: Subsets
    Generate all subsets (power set)
    Time: O(2^n * n), Space: O(n)
    """
    result = []

    def backtrack(start, current):
        result.append(current[:])

        for i in range(start, len(nums)):
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()

    backtrack(0, [])
    return result

def subsets_with_dup(nums):
    """
    LeetCode 90: Subsets II (with duplicates)
    """
    result = []
    nums.sort()

    def backtrack(start, current):
        result.append(current[:])

        for i in range(start, len(nums)):
            # Skip duplicates
            if i > start and nums[i] == nums[i-1]:
                continue
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()

    backtrack(0, [])
    return result

# Example
nums = [1, 2, 3]
print(f"Subsets of {nums}:")
for subset in subsets(nums):
    print(f"  {subset}")

// LeetCode 78: Subsets & LeetCode 90: Subsets II
// Time: O(2^n * n), Space: O(n)
#include <vector>
#include <algorithm>

class Subsets {
public:
    static std::vector<std::vector<int>> subsets(std::vector<int>& nums) {
        std::vector<std::vector<int>> result;
        std::vector<int> current;
        backtrack(nums, 0, current, result);
        return result;
    }

    // With duplicates
    static std::vector<std::vector<int>> subsetsWithDup(std::vector<int>& nums) {
        std::sort(nums.begin(), nums.end());
        std::vector<std::vector<int>> result;
        std::vector<int> current;
        backtrackWithDup(nums, 0, current, result);
        return result;
    }

private:
    static void backtrack(std::vector<int>& nums, int start,
                          std::vector<int>& current, std::vector<std::vector<int>>& result) {
        result.push_back(current);
        for (int i = start; i < nums.size(); i++) {
            current.push_back(nums[i]);
            backtrack(nums, i + 1, current, result);
            current.pop_back();
        }
    }

    static void backtrackWithDup(std::vector<int>& nums, int start,
                                  std::vector<int>& current, std::vector<std::vector<int>>& result) {
        result.push_back(current);
        for (int i = start; i < nums.size(); i++) {
            if (i > start && nums[i] == nums[i-1]) continue;  // Skip dups
            current.push_back(nums[i]);
            backtrackWithDup(nums, i + 1, current, result);
            current.pop_back();
        }
    }
};

// LeetCode 78: Subsets & LeetCode 90: Subsets II
import java.util.*;

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

    // With duplicates
    public static List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        backtrackWithDup(nums, 0, new ArrayList<>(), result);
        return result;
    }

    private static 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++) {
            current.add(nums[i]);
            backtrack(nums, i + 1, current, result);
            current.remove(current.size() - 1);
        }
    }

    private static void backtrackWithDup(int[] nums, int start,
                                          List<Integer> current, List<List<Integer>> result) {
        result.add(new ArrayList<>(current));
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i-1]) continue;  // Skip dups
            current.add(nums[i]);
            backtrackWithDup(nums, i + 1, current, result);
            current.remove(current.size() - 1);
        }
    }
}

6. Combination Sum

Find all unique combinations that sum to a target. Unlike subsets (which enumerate all), here we prune branches where the running sum exceeds the target — this is backtracking's power over brute force. The key decision at each step: which candidate to add next (starting from index $i$ to avoid reusing earlier positions). In the "reuse allowed" variant, recurse with the same index $i$ (not $i+1$); in "use once" variants, advance to $i+1$.

def combination_sum(candidates, target):
    """
    LeetCode 39: Combination Sum
    Find combinations that sum to target (can reuse)
    Time: O(2^target), Space: O(target)
    """
    result = []

    def backtrack(start, current, remaining):
        if remaining == 0:
            result.append(current[:])
            return

        if remaining < 0:
            return

        for i in range(start, len(candidates)):
            current.append(candidates[i])
            # Can reuse same element, so pass i (not i+1)
            backtrack(i, current, remaining - candidates[i])
            current.pop()

    backtrack(0, [], target)
    return result

# Example
candidates = [2, 3, 6, 7]
target = 7
print(f"Candidates: {candidates}, Target: {target}")
print(f"Combinations:")
for combo in combination_sum(candidates, target):
    print(f"  {combo}")

// LeetCode 39: Combination Sum
// Time: O(2^target), Space: O(target)
#include <vector>

class CombinationSum {
public:
    static std::vector<std::vector<int>> combinationSum(
            std::vector<int>& candidates, int target) {
        std::vector<std::vector<int>> result;
        std::vector<int> current;
        backtrack(candidates, target, 0, current, result);
        return result;
    }

private:
    static void backtrack(std::vector<int>& candidates, int remaining, int start,
                          std::vector<int>& current, std::vector<std::vector<int>>& result) {
        if (remaining == 0) {
            result.push_back(current);
            return;
        }
        if (remaining < 0) return;

        for (int i = start; i < candidates.size(); i++) {
            current.push_back(candidates[i]);
            backtrack(candidates, remaining - candidates[i], i, current, result);  // i, not i+1
            current.pop_back();
        }
    }
};

// LeetCode 39: Combination Sum
// Time: O(2^target), Space: O(target)
import java.util.*;

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

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

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

7. N-Queens

Place $N$ queens on an $N \times N$ chessboard so no two queens attack each other (no shared row, column, or diagonal). This is the classic constraint-satisfaction backtracking problem. Place queens row by row; for each row, try each column and check if it's safe (no queen in the same column, or either diagonal). Use sets or boolean arrays to track occupied columns and diagonals. The diagonal trick: cells on the same diagonal have equal $row - col$ (main) or $row + col$ (anti-diagonal).

def solve_n_queens(n):
    """
    LeetCode 51: N-Queens
    Place n queens on n×n board with no attacks
    Time: O(n!), Space: O(n)
    """
    result = []
    board = [['.'] * n for _ in range(n)]

    # Track columns and diagonals under attack
    cols = set()
    diag1 = set()  # row - col
    diag2 = set()  # row + col

    def backtrack(row):
        if row == n:
            result.append([''.join(row) for row in board])
            return

        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue

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

            backtrack(row + 1)

            # Remove queen
            board[row][col] = '.'
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)

    backtrack(0)
    return result

# Example
n = 4
solutions = solve_n_queens(n)
print(f"{n}-Queens has {len(solutions)} solutions:")
for i, sol in enumerate(solutions):
    print(f"\nSolution {i+1}:")
    for row in sol:
        print(f"  {row}")

// LeetCode 51: N-Queens
// Time: O(n!), Space: O(n)
#include <vector>
#include <string>
#include <unordered_set>

class NQueens {
public:
    static std::vector<std::vector<std::string>> solveNQueens(int n) {
        std::vector<std::vector<std::string>> result;
        std::vector<std::string> board(n, std::string(n, '.'));
        std::unordered_set<int> cols, diag1, diag2;
        backtrack(n, 0, board, cols, diag1, diag2, result);
        return result;
    }

private:
    static void backtrack(int n, int row, std::vector<std::string>& board,
                          std::unordered_set<int>& cols,
                          std::unordered_set<int>& diag1,
                          std::unordered_set<int>& diag2,
                          std::vector<std::vector<std::string>>& result) {
        if (row == n) {
            result.push_back(board);
            return;
        }

        for (int col = 0; col < n; col++) {
            if (cols.count(col) || diag1.count(row - col) || diag2.count(row + col))
                continue;

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

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

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

// LeetCode 51: N-Queens
// Time: O(n!), Space: O(n)
import java.util.*;

class NQueens {
    public static 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<>();
        Set<Integer> diag2 = new HashSet<>();
        backtrack(n, 0, board, cols, diag1, diag2, result);
        return result;
    }

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

        for (int col = 0; col < n; col++) {
            if (cols.contains(col) || diag1.contains(row - col) || diag2.contains(row + col))
                continue;

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

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

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

8. Constraint Propagation: Pruning Smarter

The N-Queens baseline above is correct, but it discovers conflicts late: for each candidate column it asks "is this column, or either diagonal, already attacked?" one set lookup at a time, and it only rejects a choice once the loop actually reaches it. Two ideas make the search itself smarter, not just the constraint check.

Forward Checking

Plain backtracking discovers a conflict by recursing all the way down until some future assignment has no legal value left, then unwinding. Forward checking does the check the moment a variable is assigned instead: as soon as a queen is placed, its column and both diagonals are eliminated from the domain of every future row immediately, so a row that has just lost its last legal column is caught right away - before the recursion wastes time descending into it. The information does not wait to be rediscovered by brute-force recursion; it propagates forward.

The Minimum Remaining Values (MRV) Heuristic

Backtracking still has to decide which variable to branch on next. Scanning rows top-to-bottom is arbitrary - it only works for N-Queens because every row is symmetric. In general, the MRV heuristic says: branch on the most-constrained variable first, the one with the fewest legal values remaining in its domain. A variable with one legal value left (or zero) fails immediately, so finding it early kills a doomed branch before the search wastes time on easier, less-constrained variables. MRV pays off most in problems where variables are not identical, such as Sudoku's 81 cells - see the Hard exercise below.

Applying Both to N-Queens: Bitmask Attack Tracking

The baseline solution tracks attacked columns and diagonals with three sets, each membership test a hash lookup, and each placement or removal touches three separate insert/erase calls. A bitmask representation makes both the check and the update a single machine-word operation, and because setting a queen's column and diagonal bits the moment it is placed - then clearing them the moment it is removed - is itself forward checking, the domain of every future row is always current without a separate propagation pass:

cols - bit $c$ set means column $c$ is attacked by a queen already placed.
diag1 - bit $c$ set means the "/" diagonal through the current row and column $c$ is attacked; shifting it left by one bit as the row advances keeps it aligned with the next row's columns.
diag2 - bit $c$ set means the "\" diagonal through the current row and column $c$ is attacked; shifting it right by one bit keeps it aligned as the row advances.

available = ((1 << n) - 1) & ~(cols | diag1 | diag2) computes every legal column for the current row in one instruction - the forward-checked domain of "columns no placed queen has eliminated yet" - instead of looping over columns and testing each against three sets. Extracting the lowest set bit with available & (-available) and clearing it walks the legal columns one at a time. This is the same bitmask machinery covered in the bit manipulation lesson - isolating the lowest set bit, shifting masks as a frontier advances, and using bitwise AND/OR/NOT to represent set membership are exactly the techniques this optimization borrows.

Each recursive call now does a fixed number of word-sized operations regardless of $n$, so the per-node cost drops from $O(n)$ set operations to $O(1)$ bitwise operations. The number of nodes explored - still bounded by $O(n!)$ in the worst case - does not change; what changes is the constant factor per node, which is why the bitmask version is the one used once $n$ is large enough to matter.

def solve_n_queens_bitmask(n):
    """
    N-Queens with Constraint Propagation (bitmask pruning)
    Columns and both diagonals are tracked as bitmasks, updated
    incrementally as queens are placed/removed, so each placement
    check is O(1) instead of O(n) set lookups.
    Time: O(n!) branches explored, O(1) attack check per placement
    Space: O(n) recursion depth
    """
    results = []
    cols_used = [-1] * n  # cols_used[row] = column of the queen in that row

    def backtrack(row, cols, diag1, diag2):
        if row == n:
            results.append(['.' * c + 'Q' + '.' * (n - c - 1) for c in cols_used])
            return

        # Forward-checked domain: columns no queen already attacks
        available = ((1 << n) - 1) & ~(cols | diag1 | diag2)
        while available:
            bit = available & (-available)   # lowest set bit = one legal column
            available -= bit
            col = bit.bit_length() - 1
            cols_used[row] = col
            backtrack(row + 1, cols | bit, (diag1 | bit) << 1, (diag2 | bit) >> 1)

        cols_used[row] = -1

    backtrack(0, 0, 0, 0)
    return results

# Example
n = 4
solutions = solve_n_queens_bitmask(n)
print(f"{n}-Queens has {len(solutions)} solutions:")
for i, sol in enumerate(solutions):
    print(f"\nSolution {i+1}:")
    for row in sol:
        print(f"  {row}")

// N-Queens with Constraint Propagation (bitmask pruning)
// Time: O(n!) branches explored, O(1) attack check per placement
#include <vector>
#include <string>

class NQueensBitmask {
public:
    static std::vector<std::vector<std::string>> solveNQueens(int n) {
        std::vector<std::vector<std::string>> result;
        std::vector<int> colsUsed(n, -1);
        backtrack(n, 0, 0, 0, 0, colsUsed, result);
        return result;
    }

private:
    static void backtrack(int n, int row, int cols, int diag1, int diag2,
                          std::vector<int>& colsUsed,
                          std::vector<std::vector<std::string>>& result) {
        if (row == n) {
            std::vector<std::string> board;
            for (int c : colsUsed) {
                board.push_back(std::string(c, '.') + "Q" + std::string(n - c - 1, '.'));
            }
            result.push_back(board);
            return;
        }

        // Forward-checked domain: columns no queen already attacks
        int available = ((1 << n) - 1) & ~(cols | diag1 | diag2);
        while (available) {
            int bit = available & (-available);  // lowest set bit = one legal column
            available -= bit;
            int col = __builtin_ctz(bit);  // GCC/Clang intrinsic; use _BitScanForward on MSVC
            colsUsed[row] = col;
            backtrack(n, row + 1, cols | bit, (diag1 | bit) << 1, (diag2 | bit) >> 1, colsUsed, result);
        }
        colsUsed[row] = -1;
    }
};

// N-Queens with Constraint Propagation (bitmask pruning)
// Time: O(n!) branches explored, O(1) attack check per placement
import java.util.*;

class NQueensBitmask {
    public static List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        int[] colsUsed = new int[n];
        backtrack(n, 0, 0, 0, 0, colsUsed, result);
        return result;
    }

    private static void backtrack(int n, int row, int cols, int diag1, int diag2,
                                   int[] colsUsed, List<List<String>> result) {
        if (row == n) {
            List<String> board = new ArrayList<>();
            for (int c : colsUsed) {
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < n; i++) sb.append(i == c ? 'Q' : '.');
                board.add(sb.toString());
            }
            result.add(board);
            return;
        }

        // Forward-checked domain: columns no queen already attacks
        int available = ((1 << n) - 1) & ~(cols | diag1 | diag2);
        while (available != 0) {
            int bit = available & (-available);  // lowest set bit = one legal column
            available -= bit;
            int col = Integer.numberOfTrailingZeros(bit);
            colsUsed[row] = col;
            backtrack(n, row + 1, cols | bit, (diag1 | bit) << 1, (diag2 | bit) >> 1, colsUsed, result);
        }
        colsUsed[row] = -1;
    }
}

9. Exercises and Mastery

Easy

Solve LeetCode 17: Letter Combinations of a Phone Number. Backtrack over digit positions, mapping each digit to its letters and appending one character at a time, then undoing it before trying the next letter.

Medium

Solve LeetCode 79: Word Search. Backtrack over grid cells in four directions, marking each visited cell before the recursive call and unmarking it afterward, so no cell is reused twice within the same path.

Hard

Solve LeetCode 37: Sudoku Solver by applying this lesson's ideas rather than plain brute-force backtracking: maintain the set of candidate digits still legal for every empty cell (forward checking), and always fill the cell with the fewest remaining candidates next (MRV) instead of scanning cells in fixed row-major order.

Mastery challenge: Take the baseline N-Queens solution and the bitmask version, run both at increasing $n$, and measure where the constant-factor improvement from constraint propagation starts to matter in practice. Then explain, in your own words, why MRV would change the search order for Sudoku but not for N-Queens.

Review rhythm: tomorrow, reconstruct the generic backtracking template and the bitmask N-Queens trick without notes; next week, implement forward checking and MRV for Sudoku from the exercise above; several weeks later, find the same "eliminate now, branch on the most-constrained choice" idea in a new constraint-satisfaction problem. Finally, teach the difference between a plain backtracking check and constraint propagation to someone who only knows the generic template.

10. Summary Cheat Sheet

Backtracking builds candidates incrementally and undoes any choice that violates a constraint before trying the next one.
The generic template is: check for a solution, try each choice, recurse, undo.
Permutations, subsets, and combination sum are the three foundational backtracking shapes, covering orderings, power sets, and pruned sums.
N-Queens is the classic constraint-satisfaction backtracking problem, tracking attacked columns and both diagonals.
Forward checking eliminates now-invalid values from future variables' domains the moment a variable is assigned, catching conflicts before brute-force recursion reaches them.
The MRV heuristic branches on the most-constrained variable first, so failing branches die early instead of late.
Bitmasks turn N-Queens' attack checks from $O(n)$ set lookups into $O(1)$ bitwise operations, updated incrementally as queens are placed and removed.
The same domain-pruning ideas power harder CSPs like Sudoku, where forward checking and MRV matter far more than in symmetric problems like N-Queens.