Backtracking

Constraint Search

Place items one at a time, validating constraints after each placement. If constraints are violated, skip this choice (prune). Used in puzzles like Sudoku, word search, and crossword filling.

varies

O(n)

How It Works

Constraint search is the general backtracking template behind puzzle solvers: extend a partial solution one placement at a time, validate constraints immediately after each placement, and abandon the branch the instant a constraint breaks. The loop is make a choice, check feasibility, recurse deeper if feasible, then undo the choice and try the next candidate. The undo step is what distinguishes backtracking from plain DFS — shared state must return to exactly its prior form so sibling choices start clean.

Worst-case time is exponential in the number of decisions, since that is the size of the search space, but early validation transforms practical performance: rejecting a partial solution at depth d prunes the entire subtree below it. Ordering heuristics compound the effect — trying the most constrained cell or the fewest-candidate choice first fails fast and shrinks the explored tree by orders of magnitude. Space is O(depth) for the recursion and choice trail.

Step-by-Step Visualization

Generic constraint satisfaction with backtracking

PatternPlace, validate, recurse

1/3

Code

Java

static List<List<Object>> solveWithConstraints(List<Object> choices, Object constraints) {
  List<List<Object>> result = new ArrayList<>();
  backtrack(new ArrayList<>(), choices, constraints, result);
  return result;
}

static void backtrack(List<Object> path, List<Object> choices, Object constraints, List<List<Object>> result) {
  if (isComplete(path)) { result.add(new ArrayList<>(path)); return; }

  for (Object choice : getChoices(path)) {
    if (!isValid(path, choice, constraints)) continue;
    path.add(choice);
    backtrack(path, choices, constraints, result);
    path.remove(path.size() - 1);
  }
}

Tips & Gotchas

1Place items one at a time, validate after each placement

2If constraint violated, skip this choice (prune)

3The earlier you prune, the faster the search

Practice Problems

1Word Search
2N-Queens
3Sudoku Solver
4Partition to K Equal Sum Subsets
5Matchsticks to Square

About the Backtracking Pattern

Systematically explore all possible solutions by making choices one at a time. If a choice leads to a dead end, undo it (backtrack) and try the next option. Think of it as exploring a decision tree — you go deep, and come back up when stuck.

Key insight

Every recursive solution has: base case, recursive case, and combining step. For backtracking, add: make choice → recurse → undo choice. Prune early to avoid TLE.

Common Recursion Interview Problems

Subsets
Permutations
Combination Sum
N-Queens
Word Search
Generate Parentheses
Letter Combinations of Phone Number

Frequently Asked Questions

What is the difference between backtracking and brute-force enumeration?

Brute force generates every complete candidate and tests it at the end; backtracking tests constraints on partial candidates and abandons infeasible prefixes immediately. Both have exponential worst cases, but pruning partial solutions can eliminate the vast majority of the search tree in practice.

Why must state be restored exactly after each recursive call?

Sibling branches assume they start from the same parent state. If a placement marks a grid cell or updates a running sum and the undo is skipped or incomplete, later branches operate on corrupted state and silently produce wrong or missing solutions. Every mutation before the recursive call needs a mirrored reversal after it.

When should I reach for backtracking instead of dynamic programming?

Use backtracking when you must enumerate the actual solutions or when constraints couple choices in ways that resist a compact state (grids, orderings, exact placements). DP fits when the problem only asks for a count or optimum and overlapping subproblems can be described by a small state, letting you avoid re-exploring.