Module P-7 — Backtracking: Exploring the Solution Space
What this module covers: Some problems can't be solved by a direct formula — they require trying a choice, seeing where it leads, and undoing it if it doesn't work out. This module covers backtracking: recursive exploration (Module P-1) of every possible path through a decision space, pruning branches that can't possibly succeed, and restoring state before trying the next option.
The Shape of Backtracking
Every backtracking algorithm follows the same skeleton: make a choice, recurse into the consequences of that choice, then undo the choice before trying the next one — so the next branch starts from a clean slate, not contaminated by the previous attempt.
typescript
The path.pop() after the recursive call is the entire idea in one line: without it, every subsequent branch of the loop would incorrectly still include a choice from a path that's already been fully explored and abandoned. This "undo before trying the next option" step is what separates backtracking from plain recursive exploration (Module P-1) — it's recursion with an explicit discipline about cleaning up after each attempt.
Analogy: Backtracking is exploring a maze by walking down a corridor, marking it as "tried" as you go. If it's a dead end, you don't teleport back to the start — you walk back out the way you came, un-marking as you retreat, so the next corridor you try starts from a genuinely clean position, not one still cluttered with your last attempt's chalk marks.
Generating All Subsets (the Power Set)
For each element, you have exactly two choices: include it, or don't. Backtracking explores both branches for every element:
typescript
Every element doubles the number of possible subsets (include or exclude), so this produces and visits all 2ⁿ subsets — the O(2ⁿ) complexity class from Module F-1's table, here not as an accidental performance trap (as it was for naive Fibonacci in Module P-1) but as the genuinely correct, unavoidable cost of enumerating every subset, since there are exactly 2ⁿ of them to produce.
Why [...current], not current, gets pushed into result:current is a single array, mutated in place throughout the whole recursion — pushing the reference itself would mean every entry in result ends up pointing at the same array, which keeps changing after being "recorded." Copying it at the moment of recording freezes a snapshot of its contents at that exact instant.
Generating All Permutations
Permutations require a different kind of choice-tracking: instead of "include or exclude," every element must be used exactly once, in every possible order — which means tracking which elements have already been placed.
typescript
The used.has(num) check is pruning — cutting off a branch of exploration before wasting time recursing into it, because it's already known to be invalid (this element is already placed elsewhere in the current path). This is the piece that distinguishes backtracking from blind brute-force enumeration: don't just try everything and check validity at the end — skip invalid choices as early as possible, so the recursion never even descends into a doomed branch.
Pruning More Aggressively: N-Queens
N-Queens — place N queens on an N×N board so that no two attack each other — is the canonical example of pruning making an otherwise-infeasible search tractable. A queen attacks along its row, column, and both diagonals, so at each step, only positions not currently under attack are worth trying at all:
typescript
Without the three Sets checking column and diagonal conflicts, this would need to explore every possible placement of every queen and check validity only at the very end — far more branches than actually need to be visited. By pruning at every single step (checking conflicts before recursing deeper, not after), entire subtrees of hopeless placements are skipped before any time is spent exploring them — the difference between a search that finishes instantly and one that's still running for large n.
Where This Shows Up in Your Stack
Generating all combinations of feature flags or A/B test variants for exhaustive testing is exactly the subsets pattern — every flag is an independent include/exclude choice.
Constraint satisfaction in configuration validation (assigning ports, IP ranges, or resource allocations without conflicts) follows the N-Queens shape directly: try an assignment, check it against existing constraints, backtrack if it conflicts.
Route-finding with constraints (delivery routing with must-visit stops, or a game AI exploring possible move sequences) is backtracking with a specific goal condition replacing "record every full path" — explore, prune paths that already violate a constraint, backtrack from dead ends.
Sudoku solvers follow the identical three-part shape as N-Queens: place a candidate number, check it against row/column/box constraints (a slightly more elaborate version of the column/diagonal checks above), recurse, and backtrack on failure.
Summary
Backtracking is recursion with a strict undo discipline: make a choice, recurse into its consequences, then explicitly restore state before trying the next choice — so branches never contaminate each other.
Generating all subsets is an include/exclude choice per element, producing all 2ⁿ subsets — an unavoidable O(2ⁿ) cost, since that many subsets genuinely exist.
Generating all permutations tracks which elements are already placed (Module F-4's hash set, O(1) membership check), skipping — pruning — choices that are already invalid rather than generating and discarding them after the fact.
N-Queens shows pruning at its most aggressive: checking column/diagonal conflicts before recursing avoids ever exploring huge subtrees of positions that were doomed from the first placement.
The general shape — choose, recurse, prune invalid branches early, undo — solves constraint satisfaction problems across configuration validation, routing, and puzzle-solving.
The next module, Sorting I: O(n²) Sorts and Why They're Slow, shifts from exploring solution spaces to ordering data — starting with the simplest sorts, specifically to understand exactly why the faster ones (Modules P-9, P-10) are worth the added complexity.
Knowledge Check
In the subsets function, why is path.pop() (or current.pop()) called immediately after the recursive call, rather than only at the very end of the function?
In permutations, what specific role does the used.has(num) check play, and why is checking it referred to as "pruning" rather than just "validation"?
In solveNQueens, why are cols, diagonals, and antiDiagonals checked before the recursive call to backtrack(row + 1), rather than validating the entire board only after all n queens have been placed?
Test your knowledge with more question sets
Sign in to access a wider variety of questions and get notified when new practice sets are added to this module.
functionbacktrack(path:number[], choices:number[]):void{if(/* some end condition */false){// record path as a valid solutionreturn;}for(const choice of choices){ path.push(choice);// make the choicebacktrack(path, choices);// explore the consequences path.pop();// undo the choice — restore state for the next iteration}}
functionsubsets(nums:number[]):number[][]{const result:number[][]=[];const current:number[]=[];functionbacktrack(index:number):void{if(index === nums.length){ result.push([...current]);// record a copy — `current` will keep changing after thisreturn;}// Choice 1: exclude nums[index]backtrack(index +1);// Choice 2: include nums[index] current.push(nums[index]);backtrack(index +1); current.pop();// undo — so the next branch doesn't see this element included}backtrack(0);return result;}subsets([1,2]);// [[], [2], [1], [1, 2]]
functionpermutations(nums:number[]):number[][]{const result:number[][]=[];const current:number[]=[];const used =newSet<number>();// Module F-4 — O(1) membership checkfunctionbacktrack():void{if(current.length === nums.length){ result.push([...current]);return;}for(const num of nums){if(used.has(num))continue;// pruning — skip choices that are already invalid used.add(num); current.push(num);backtrack(); current.pop();// undo used.delete(num);// undo}}backtrack();return result;}permutations([1,2,3]);// [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]
functionsolveNQueens(n:number):number[][]{const results:number[][]=[];const cols =newSet<number>();const diagonals =newSet<number>();// row - col is constant along a "/" diagonalconst antiDiagonals =newSet<number>();// row + col is constant along a "\" diagonalconst placement:number[]=[];// placement[row] = column of the queen in that rowfunctionbacktrack(row:number):void{if(row === n){ results.push([...placement]);return;}for(let col =0; col < n; col++){if(cols.has(col)|| diagonals.has(row - col)|| antiDiagonals.has(row + col)){continue;// pruned — this position is already under attack, don't even explore it} cols.add(col); diagonals.add(row - col); antiDiagonals.add(row + col); placement.push(col);backtrack(row +1);// Undo all four pieces of state before trying the next column cols.delete(col); diagonals.delete(row - col); antiDiagonals.delete(row + col); placement.pop();}}backtrack(0);return results;}