Repository navigation
018 — DFS and Backtracking
Binary Search cuts a search space in half without ever exploring most of it. DFS and Backtracking is the opposite instinct: when there's no shortcut and you genuinely need to explore every possible path through a decision tree — but explore it cleverly, undoing each choice the moment it stops paying off, instead of copying the entire state for every branch.
The Stacks chapter covered the data structure itself — LIFO push/pop, where only the most recently added item is ever accessible. This chapter is about recognizing when that same discipline shows up implicitly: every recursive backtrack/dfs call is managed by the language's own call stack, so "choose, explore, un-choose" is really just push and pop happening for free, one stack frame at a time.
Picture exploring a pitch-black maze with a ball of string tied to the entrance, unspooling it as you walk. At every junction, you commit to one path — string trailing behind you — and keep going deeper until you either find the exit or hit a dead end. Hit a dead end, and you don't need a map or a memory of the whole maze: you just reel the string back in to the last junction, and try the next unexplored path from there. The string is the whole trick — it lets you "undo" your way back to any earlier decision point cheaply, one step at a time, without ever losing track of where you are.
That's backtracking layered on top of DFS: go deep, commit to a choice, recurse — and the instant a branch is exhausted or invalid, undo that one choice and try the next, rather than starting over from scratch.
DFS and Backtracking is a strong reach when you see:
- "All possible" — "all subsets," "all permutations," "all combinations," "all valid arrangements" — any phrasing asking for the complete enumeration of some structure, not just one answer or a count.
- "Generate" combined with a validity constraint — "generate all valid parentheses combinations," "generate all paths from root to leaf that sum to a target" — you're building up a candidate incrementally and need to check partial validity along the way, abandoning early when a partial candidate can't possibly become valid.
- Grid/board search with a "visited" requirement — "word search," "number of islands," "solve a Sudoku/N-Queens board" — DFS explores one path fully (marking cells visited) before backing out and un-marking them to try a different path.
- Tree/graph problems asking for every root-to-leaf path, or "does a path exist satisfying condition X" where you need to actually construct the path, not just detect it.
The unifying tell: the problem wants you to build up a solution incrementally, choice by choice, and some choices turn out to be dead ends only after you've gone further down that branch — which means you need a cheap way to undo a choice and try the sibling instead.
Generating all subsets of [1, 2] — at each element, branch into "include it" and "exclude it," backtracking after each branch:
backtrack(start=0, path=[])
RECORD [] ← every node is a valid subset, record on entry
i=0: choose 1 → path=[1]
backtrack(start=1, path=[1])
RECORD [1]
i=1: choose 2 → path=[1,2]
backtrack(start=2, path=[1,2])
RECORD [1,2]
(start == count, loop body never runs)
undo → path=[1]
undo → path=[]
i=1: choose 2 → path=[2]
backtrack(start=2, path=[2])
RECORD [2]
(loop body never runs)
undo → path=[]
Recorded, in order: [], [1], [1,2], [2] — all 2² = 4 subsets.
The path array is mutated in place the whole time — append before
recursing, removeLast() right after, so only ONE array ever exists.
func backtrackTemplate(_ candidates: [Int]) -> [[Int]] {
var results: [[Int]] = []
var path: [Int] = []
func backtrack(_ start: Int) {
// 🔧 Fill in: record `path` here if EVERY node is a valid answer (subsets),
// or guard this behind a completion check if only certain nodes are (permutations
// of fixed length, combinations that must sum to a target, etc).
results.append(path) // record a COPY — `path` keeps mutating after this
for i in start..<candidates.count {
// 🔧 Fill in: any pruning check — skip this candidate if it can't lead
// to a valid answer (already used, breaks a constraint, etc).
path.append(candidates[i]) // choose
backtrack(i + 1) // explore deeper with this choice made
path.removeLast() // un-choose — THE core backtracking step
}
}
backtrack(0)
return results
}The skeleton never changes: a mutable path shared across the whole recursion, a recording step (unconditional here, since every subset — including the empty one — is valid), and a loop over remaining choices that appends-recurses-removes for each one. The "un-choose" line (path.removeLast(), or unmarking a visited cell, or restoring a swapped character) is what makes this backtracking rather than plain DFS — it's what lets one path array serve every branch of the tree instead of allocating a new array per branch. For problems where only some nodes are valid answers (permutations, "combinations that sum to target"), move the recording behind a completion check instead of doing it unconditionally.
Word Search — given an m x n grid of characters and a word, determine if the word exists in the grid, constructed from letters of sequentially adjacent cells (horizontally or vertically), using each cell at most once.
func exist(_ board: [[Character]], _ word: String) -> Bool {
var grid = board
let target = Array(word)
let rows = grid.count
let cols = grid[0].count
func backtrack(_ row: Int, _ col: Int, _ index: Int) -> Bool {
// Base case: matched every character in the word.
if index == target.count { return true }
// Pruning: out of bounds, or this cell doesn't match / was already used.
guard row >= 0, row < rows, col >= 0, col < cols,
grid[row][col] == target[index] else {
return false
}
let original = grid[row][col]
grid[row][col] = "#" // mark visited — choose
let found = backtrack(row + 1, col, index + 1)
|| backtrack(row - 1, col, index + 1)
|| backtrack(row, col + 1, index + 1)
|| backtrack(row, col - 1, index + 1)
grid[row][col] = original // un-choose — restore for other branches
return found
}
for r in 0..<rows {
for c in 0..<cols {
if backtrack(r, c, 0) { return true }
}
}
return false
}
// smoke test
let board: [[Character]] = [
["A", "B", "C", "E"],
["S", "F", "C", "S"],
["A", "D", "E", "E"]
]
print(exist(board, "ABCCED")) // true
print(exist(board, "SEE")) // true
print(exist(board, "ABCB")) // falseMapped onto the template: path becomes implicit in the grid itself — instead of an array being appended to, a cell is temporarily overwritten with "#" to mark it "in use" (choose), and restored to its original value the instant that branch returns (un-choose). The base case (index == target.count) and the pruning guard play the exact same roles as the template's completion check and skip-condition — only the shape of the "candidates" (grid neighbors instead of a flat array) changed.
DFS and Backtracking is exploring a maze with a ball of string — commit to a path, go as deep as it leads, and the moment it's a dead end, reel back to the last junction and try the next one.
A problem asks for "all valid combinations of k numbers from 1 to 9 that sum to n, using each number at most once." Sketch how you'd adapt the backtrackTemplate skeleton above: what goes in the base case, what pruning check would you add inside the loop to avoid wasted recursion, and why does pruning matter more here than it did for generating all subsets?