06. DFS / Backtracking

TL;DR

Depth-first search explores as far as possible before retreating: on a graph you mark visited state to avoid cycles; on a tree the parent path is often the only “visited” you need. Backtracking is DFS over decision space: at each step you choose (mutate a shared path/state), recurse, then un-choose to restore the world for the next branch. That do/undo symmetry is what keeps subsets, permutations, and constraint puzzles like N-Queens correct without cloning entire worlds every step.

Recognition Cues

Phrases: “all subsets/combinations/permutations,” “build incrementally,” “can place/non-attacking,” “fill the board,” “word search on grid,” “islands/components,” “path from root to leaf with sum,” “cycle in graph” (visited + stack color may apply).
Inputs: adjacency list or grid; array to partition; phone pad letters; n for board size; tree nodes.
Outputs: list of built objects, count, boolean reachability, or a single path.

Diagram

Pattern control flow (customize nodes for this pattern). camelCase node IDs.

Loading diagram…

Mental Model

Graph DFS: you are walking a maze; visited is chalk on the floor so you do not walk the same room twice in the same search context.
Tree DFS: no global cycle from a child back to an ancestor in a standard tree, so you often only need the recursion stack; some problems still need a path set for “no duplicate value on path” style constraints.
Backtracking: the recursion stack is a time machine; every mutate before recurse must be reverted after so the next sibling option starts from a clean snapshot. Choose / explore / un-choose mirrors push / call / pop on an explicit stack.

Generic Recipe

Graph (grid): mark start visited; for each neighbor in bounds and passable, if not visited, recurse; on return, unmark only if the problem needs “count paths” or similar (otherwise keep visited for single connected component flood fill).
Tree (path collection): carry currentPath, on visit append value, at leaf or when predicate matches record a copy; after children return, remove last element (backtrack the path).
Backtracking (combinatorics): sort or index for dedupe if input has duplicates; loop options; place choice in shared buffer, recurse(nextIndex), remove choice.
N-Queens / constraints: isValid checks only what prior rows/columns/diagonals need; place row by row; undo placement when backtracking.
Return accumulated results or update a best/global answer with a clear invariant.

Complexity

Time: often exponential in combinatorial backtracking (e.g. subsets O(n·2^n) to output all); graph DFS is O(V + E) for visiting each vertex/edge once in the typical case.
Space: O(h) recursion depth (h = height, or n for board size); plus O(V) for visited set in graph; output size is additional when you materialize all solutions.

Generic Code Template

Go

package main

// Graph node for adjacency-list DFS.
type graphNode struct {
	Val       int
	Neighbors []*graphNode
}

func clonePath(path []int) []int {
	copied := make([]int, len(path))
	copy(copied, path)
	return copied
}

// Graph DFS with visited set; returns a label order for demo.
func dfsGraph(start *graphNode, visited map[*graphNode]bool, order *[]int) {
	if start == nil || visited[start] {
		return
	}
	visited[start] = true
	*order = append(*order, start.Val)
	for _, neighbor := range start.Neighbors {
		dfsGraph(neighbor, visited, order)
	}
}

// TreeNode for binary tree DFS.
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func dfsTreePaths(root *TreeNode) [][]int {
	var allPaths [][]int
	var path []int
	var walk func(node *TreeNode)
	walk = func(node *TreeNode) {
		if node == nil {
			return
		}
		path = append(path, node.Val)
		if node.Left == nil && node.Right == nil {
			allPaths = append(allPaths, clonePath(path))
		} else {
			walk(node.Left)
			walk(node.Right)
		}
		path = path[:len(path)-1]
	}
	walk(root)
	return allPaths
}

// Backtracking: subsets of distinct indices.
func subsets(nums []int) [][]int {
	var result [][]int
	var current []int
	var backtrack func(startIndex int)
	backtrack = func(startIndex int) {
		copied := make([]int, len(current))
		copy(copied, current)
		result = append(result, copied)
		for index := startIndex; index < len(nums); index++ {
			current = append(current, nums[index])
			backtrack(index + 1)
			current = current[:len(current)-1]
		}
	}
	backtrack(0)
	return result
}

func main() {
	_ = subsets([]int{1, 2, 3})
	_ = dfsTreePaths(&TreeNode{Val: 1, Left: &TreeNode{Val: 2}, Right: &TreeNode{Val: 3}})
	nodeThird := &graphNode{Val: 3}
	nodeSecond := &graphNode{Val: 2, Neighbors: []*graphNode{nodeThird}}
	nodeFirst := &graphNode{Val: 1, Neighbors: []*graphNode{nodeSecond}}
	var visitOrder []int
	dfsGraph(nodeFirst, map[*graphNode]bool{}, &visitOrder)
}

JavaScript

function dfsGraph(start, visited = new Set()) {
  const order = [];
  function visit(node) {
    if (!node || visited.has(node)) return;
    visited.add(node);
    order.push(node.val);
    for (const neighbor of node.neighbors) visit(neighbor);
  }
  visit(start);
  return order;
}

function dfsTreePaths(root) {
  const allPaths = [];
  const path = [];
  function walk(node) {
    if (!node) return;
    path.push(node.val);
    if (!node.left && !node.right) {
      allPaths.push([...path]);
    } else {
      walk(node.left);
      walk(node.right);
    }
    path.pop();
  }
  walk(root);
  return allPaths;
}

function subsets(nums) {
  const result = [];
  const current = [];
  function backtrack(startIndex) {
    result.push([...current]);
    for (let index = startIndex; index < nums.length; index++) {
      current.push(nums[index]);
      backtrack(index + 1);
      current.pop();
    }
  }
  backtrack(0);
  return result;
}

Variants

Graph / grid: 4- or 8-direction; boundary “flood from edge” (surrounded regions); clone graph (map old→new, DFS copy).
Tree: preorder/inorder/postorder; path sum with path backtracking; same tree as parallel DFS.
Backtracking: permutations (use used boolean array); combinations (next start index); duplicates (sort, skip nums[index] == nums[index-1] when index > start); word search (grid DFS + undo visited cell per path branch).
N-Queens: row-wise placement, column and diagonal attack sets; undo on backtrack.

Representative Problems

200. Number of Islands — grid DFS + visited
78. Subsets — classic backtracking
51. N-Queens — constraint backtracking
79. Word Search — grid DFS with choose/undo per cell
113. Path Sum II — tree path backtracking

Anti-patterns

Forgetting to undo after recursion in backtracking, corrupting sibling branches.
Sharing the same slice without copy when storing “snapshots” in the result (aliasing bugs).
Graph DFS without visited on general graphs → infinite recursion on cycles.
Copying the entire prefix on every step when a single shared buffer + undo is enough (unnecessary allocation pressure).

On this page