DFS and Backtracking Pattern

Relevant source files

Purpose and Scope

This document explains the Depth-First Search (DFS) and backtracking algorithmic pattern as implemented in the repository's problem solutions. DFS is a fundamental graph/tree traversal technique, while backtracking extends DFS to explore solution spaces by building candidates incrementally and abandoning them when they cannot lead to valid solutions. This page covers recursive tree traversal, constraint satisfaction problems, and combinatorial search implementations.

For array manipulation techniques, see Two Pointers Pattern. For optimization problems with overlapping subproblems, see Dynamic Programming Pattern. For exhaustive state space exploration without pruning, see standard DFS implementations in tree/graph problems.

Overview

DFS and backtracking share a common recursive structure but differ in their goals:

DFS: Explores a graph or tree by going as deep as possible before backtracking. Used for traversal, path finding, and connectivity analysis.
Backtracking: Systematically explores all potential solutions by making choices, recursing, and undoing choices (backtracking) when constraints are violated. Used for permutations, combinations, N-Queens, sudoku solving, and constraint satisfaction problems.

Both patterns rely on:

Recursive function calls to explore deeper states
Base cases to terminate recursion
State restoration when returning from recursive calls (explicit in backtracking)

Key characteristics in this repository:

Problems are organized across solution/, lcci/, lcof/, and lcp/ directories
Solutions typically provide implementations in 10+ programming languages
DFS solutions often appear in tree and graph problems (problem categories marked with tags like "Tree", "Graph", "Backtracking")
Backtracking solutions commonly include constraint checking and pruning logic

Sources: Overall repository structure from provided diagrams

DFS Fundamentals

DFS Traversal Structure

Sources: General DFS pattern

Tree DFS Example: Lowest Common Ancestor

The repository implements tree DFS traversal in problems like the Lowest Common Ancestor (LCA) problem, which demonstrates post-order DFS with result propagation.

Implementation in Python:

lcci/04.08.First Common Ancestor/Solution.py10-17

Implementation in Java:

lcci/04.08.First Common Ancestor/Solution.java10-18

Implementation in C++:

lcci/04.08.First Common Ancestor/Solution.cpp10-20

Key DFS characteristics demonstrated:

Base case: Returns immediately when root is None/null or matches target nodes
Recursive exploration: Explores left subtree, then right subtree
Result aggregation: Combines information from both subtrees to determine the ancestor
Post-order traversal: Processes node after visiting children

The time complexity is $O(n)$ where $n$ is the number of tree nodes, as each node is visited exactly once. Space complexity is $O(h)$ for the recursion stack, where $h$ is the tree height.

Sources: lcci/04.08.First Common Ancestor/README.md70-79 lcci/04.08.First Common Ancestor/README_EN.md70-79 lcci/04.08.First Common Ancestor/Solution.py1-18 lcci/04.08.First Common Ancestor/Solution.java1-19 lcci/04.08.First Common Ancestor/Solution.cpp1-21

Backtracking Pattern Structure

Backtracking Template

Backtracking problems follow a standard template that explores the solution space systematically:

Generic backtracking pseudocode structure:

Sources: Standard backtracking pattern

State Management in Backtracking

Component	Purpose	Example
Current Path	Tracks choices made so far	List of queens' positions, string partition indices
State	Represents problem constraints	Board configuration, used characters set
Choices	Available options at current step	Available board positions, remaining characters
Constraint Check	Validates whether choice is legal	No two queens attack each other, palindrome validation
State Restoration	Undoes choice when backtracking	Remove queen from board, remove from used set

Sources: General backtracking concepts

Common Backtracking Scenarios

N-Queens Problem (Eight Queens)

The classic N-Queens problem places N queens on an N×N chessboard such that no two queens attack each other. This demonstrates pure backtracking with constraint checking.

Problem structure:

State: Current board configuration with placed queens
Choices: Available columns in the current row
Constraints: No two queens in same row, column, or diagonal
Goal: All N queens placed successfully

Backtracking approach:

Typical implementation structure:

Complexity:

Time: $O(N!)$ - at most $N$ choices in first row, $N-2$ in second, etc.
Space: $O(N)$ for recursion depth and state tracking sets

Sources: Standard N-Queens backtracking pattern

String Partitioning (Palindrome Partition)

String partitioning problems use backtracking to split strings into valid substrings, with constraint checking at each partition point.

Problem structure:

State: Current position in string
Choices: Where to make the next cut
Constraints: Resulting substring must satisfy condition (e.g., is palindrome)
Goal: Reached end of string

Decision tree example for "aab":

Implementation pattern:

Sources: Standard palindrome partition backtracking pattern

Combinatorial Problems

Backtracking excels at generating combinations, permutations, and subsets:

Problem Type	State	Choices	Constraint
Combinations	Current combination, start index	Remaining elements	No duplicates, size limit
Permutations	Current permutation, used set	Unused elements	Each element used once
Subsets	Current subset, index	Include or skip element	Size constraints if any
Combination Sum	Current sum, combination	Candidates (possibly reusable)	Sum equals target

Common pattern for combinations:

Sources: Standard combinatorial backtracking patterns

Implementation Guidelines

Code Structure Across Languages

The repository provides multi-language implementations following consistent patterns. Here's how key components map across languages:

Recursion and base cases:

Language	Base Case Check	Recursion	Example Reference
Python	`if root is None or root in [p, q]:`	`left = self.lowestCommonAncestor(root.left, p, q)`	lcci/04.08.First Common Ancestor/Solution.py10-14
Java	`if (root == null \|\| root == p \|\| root == q)`	`TreeNode left = lowestCommonAncestor(root.left, p, q);`	lcci/04.08.First Common Ancestor/Solution.java11-15
C++	`if (!root \|\| root == p \|\| root == q)`	`TreeNode* left = lowestCommonAncestor(root->left, p, q);`	lcci/04.08.First Common Ancestor/Solution.cpp12-16
Go	`if root == nil \|\| root == p \|\| root == q`	`left := lowestCommonAncestor(root.Left, p, q)`	lcci/04.08.First Common Ancestor/Solution.go5-9
JavaScript	`if (!root \|\| root === p \|\| root === q)`	`const left = lowestCommonAncestor(root.left, p, q);`	lcci/04.08.First Common Ancestor/Solution.js7-11

State management and backtracking:

For backtracking problems with explicit state restoration:

Sources: lcci/04.08.First Common Ancestor/Solution.py1-18 lcci/04.08.First Common Ancestor/Solution.java1-19 lcci/04.08.First Common Ancestor/Solution.cpp1-21 lcci/04.08.First Common Ancestor/Solution.go1-17 lcci/04.08.First Common Ancestor/Solution.js1-13

Performance Considerations

Time complexity patterns:

Pattern	Complexity	Reasoning
Tree DFS	$O(n)$	Visit each node once
N-Queens	$O(N!)$	Factorial branching with pruning
Subsets	$O(2^n)$	Binary choice for each element
Permutations	$O(n \cdot n!)$	$n!$ permutations, $O(n)$ to copy each
Combination Sum	$O(n^{target/min})$	Branching factor $n$, depth $target/min$

Space complexity:

Recursion stack depth: $O(h)$ for trees (height), $O(n)$ for backtracking (max depth)
State storage: Varies by problem (e.g., $O(n)$ for tracking used elements, board state)

Optimization techniques:

Early pruning: Check constraints before recursing (reduces explored branches)
Memoization: Cache results for overlapping subproblems (converts to DP)
Iterative approaches: Use explicit stack for DFS when recursion depth is concern
Constraint ordering: Process most restrictive constraints first

Sources: lcci/04.08.First Common Ancestor/README.md29-31 lcci/04.08.First Common Ancestor/README_EN.md77-79

Common Pitfalls and Solutions

Pitfall	Problem	Solution
Forgetting to backtrack	State carries over between branches	Always restore state after recursion
Shallow copy in solutions	Modifications affect recorded solutions	Use `path[:]` or `path.copy()` in Python
Redundant constraint checks	Checking constraints after making choice	Check constraints before making choice
Inefficient pruning	Exploring invalid branches too deep	Add constraint checks at each level
Stack overflow	Recursion too deep	Consider iterative approach or increase stack limit

Example of correct backtracking pattern:

Sources: General backtracking best practices

Relationship to Other Patterns

When to use DFS/Backtracking:

Tree/graph traversal and connectivity
Finding all solutions (combinations, permutations, subsets)
Constraint satisfaction problems (N-Queens, sudoku)
Path finding with exploration
Problems requiring exhaustive search with pruning

When to use alternatives:

Dynamic Programming: Overlapping subproblems with optimal substructure
Binary Search: Sorted input with monotonic decision function
Two Pointers: Linear structures with specific ordering properties
Hash Table: Constant-time lookup without exploration needed

Sources: Overall repository structure and pattern relationships from page TOC