Back to Study Material Data Structures and Algorithms

Backtracking

Backtracking is a systematic way to explore all possible candidates for a solution by building candidates incrementally and abandoning (backtracking from) ...

Backtracking

The Backtracking Paradigm

Backtracking is a systematic way to explore all possible candidates for a solution by building candidates incrementally and abandoning (backtracking from) a candidate as soon as it is determined that the candidate cannot lead to a valid complete solution. It is essentially depth-first search on the implicit solution space tree.

The general structure is: choose a candidate extension to the current partial solution; check if it violates any constraints (pruning condition); if it does, skip this choice and try the next; if it does not, apply the choice, recurse, and after returning undo the choice (backtrack). This "choose, explore, unchoose" pattern is the hallmark of backtracking.

The power of backtracking lies in pruning: by detecting infeasibility early, you avoid exploring enormous subtrees of the solution space. Without pruning, backtracking degenerates to brute-force enumeration. With effective pruning, it can solve problems with enormous search spaces in practical time.

A worked example: generate all permutations of [1, 2, 3]. At each step, choose an unvisited element, add it to the current permutation, recurse, then remove it. The recursion tree has 3! = 6 leaves: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]. All 6 are valid, so no pruning occurs here. But for a constrained permutation (e.g., no two adjacent elements differ by 1), pruning would cut many branches.

Time complexity in the worst case (no pruning) is O(n!) for permutations, O(2^n) for subset enumeration. Effective pruning makes actual runtime far better in practice, though the worst case remains exponential.

Interview tip: When implementing backtracking, always separate the "check constraint" step from the "apply choice" step. This separation makes it easy to add new constraints without restructuring the recursion, and it makes your code easier to reason about during an interview.

Constraint Propagation and Pruning Strategies

Pruning is what separates practical backtracking from naive enumeration. A pruning condition (also called a constraint check) examines the current partial solution and determines whether any complete extension of it can possibly be valid. If no valid completion exists, the entire subtree is pruned.

Simple pruning checks only the most recent choice: does this choice violate a constraint with any previously made choice? This is a forward check and catches the most common violations. For the N-queens problem, simple pruning checks whether the newly placed queen conflicts with any previously placed queen (same row, column, or diagonal).

Advanced pruning uses constraint propagation: after making a choice, deduce its implications for future choices and prune based on those implications. In Sudoku solving, placing a digit in a cell propagates to eliminate that digit from the same row, column, and 3x3 box in all future cells. This can cascade: if a row now has only one empty cell with only one remaining valid digit, that digit is forced, further narrowing the search.

Ordering heuristics also reduce search time significantly. For constraint satisfaction problems, the fail-first principle suggests choosing the variable with the fewest remaining valid values next. This causes failures to be detected sooner, pruning branches earlier in the search.

Bounding is another pruning strategy used in branch-and-bound: compute an upper bound on the best solution reachable from the current partial solution. If this upper bound is worse than the best complete solution found so far, prune the current branch.

Interview tip: For any backtracking problem in an interview, implement simple constraint checking first and verify it works correctly. Then discuss how you would add more aggressive pruning if the solution is too slow. This demonstrates a progressive engineering mindset rather than overengineering from the start.

Backtracking vs. Dynamic Programming

Backtracking and dynamic programming both solve problems by breaking them into smaller pieces, but they are suited to fundamentally different problem types. Understanding this distinction prevents you from applying the wrong technique.

Dynamic programming is appropriate when sub-problems overlap and optimal substructure holds — you need the globally optimal solution and sub-problem solutions combine to give the overall solution. Backtracking is appropriate when you need to enumerate all valid solutions (or find any one valid solution) and the problem has no clear optimal substructure — choices are discrete and must satisfy explicit constraints.

For example: finding the length of the longest increasing subsequence has overlapping sub-problems and optimal substructure — use DP. Finding all increasing subsequences of a given length requires enumerating specific sequences — use backtracking. The problems sound similar but are structurally different.

In practice, some problems require both. A backtracking search may use memoization to avoid re-exploring identical partial states, essentially converting it into a constrained DP. This hybrid approach appears in problems like counting valid placements (N-queens counting, valid Sudoku count) where memoization can detect repeated board configurations.

State space representation distinguishes the two: DP stores a compact state (often an integer or array index) and looks up precomputed results. Backtracking carries the full partial solution state and cannot generally be memoized because the number of distinct partial solutions may be exponential.

Interview tip: If an interviewer asks "can you use DP here instead of backtracking?" the key question is whether sub-problems repeat. If the same partial state can be reached by multiple paths through the search tree, memoization is possible and can improve performance. State this analysis explicitly.