Skip to main content

Backtracking, Graphs, and DP

Backtracking

Backtracking heavily relies on a thorough understanding of recursion. We suggest skimming through this comprehensive recursion lesson to refresh key concepts before diving into backtracking problems.

Backtracking is a systematic, recursive algorithmic technique for solving constraint satisfaction problems by building solutions incrementally and abandoning partial solutions ("backtracking") as soon as it’s clear they won't lead to a valid full solution. It explores all potential candidates but prunes invalid paths early, making it more efficient than brute force in many cases.

When to use: Problems where all or some solutions to a problem with constraints are needed.

Classic use cases: permutations, combinations, subsets, N-Queens, Sudoku, word search, maze/pathfinding.

Backtracking patterns

1. General structure

  • Choose: Select one candidate from available options.
  • Explore: Recurse with the chosen candidate added to the current partial solution.
  • Backtrack: Remove the candidate before exploring the next (backtracking step).
  • Base case: When a valid complete solution is formed or all options are exhausted.
def backtrack(path, options): if goal_reached(path): output_solution(path) return for option in options: if is_valid(path, option): path.append(option) # Choose backtrack(path, options) # Explore path.pop() # Unchoose (backtrack)

2. Candidate generation

  • Generate all possible choices for the next step.
  • Use auxiliary data structures like visited or bitmasks to avoid repeats.

Examples: selecting unused characters for permutations, placing queens in rows/columns.

3. Pruning early

  • Check constraints before recursing to prune branches early and avoid unnecessary work (e.g., partial sums, invalid placements).
  • This can reduce exponential growth significantly.

Time complexity

  • Backtracking explores possible choices at each step, often leading to exponential time in the worst case.
  • For a problem with branching factor k and depth n, worst-case complexity is generally O(k^n).

Space complexity

  • The recursion call stack, proportional to the maximum depth, usually O(n)

Common pitfalls & tips

  • Forgetting to backtrack: Always undo changes to state (e.g., removing from path or resetting visited) before trying the next candidate.
  • Unnecessary computations: Use early validity checks and prune aggressively.
  • Deep recursion: Watch out for stack overflows in languages without tail recursion optimizations or use iterative backtracking if needed.
  • Handling duplicates: For problems requiring unique solutions, sort options or skip duplicates to avoid repeated outputs.
  • Base cases: Clearly define when a solution is complete to avoid infinite recursion or premature termination.

Backtracking Cheatsheet

Practice problems

Graphs

A graph is a data structure consisting of a set of vertices (or nodes) connected by edges. Graphs model pairwise relationships and networks such as social connections, road maps, communication networks, scheduling tasks, and more. Vertices represent entities (e.g., people, cities), and edges represent relationships or connections.

Types of graphs

  • Undirected graph: Edges have no direction; relationships are mutual.
  • Directed graph (Digraph): Edges have direction, representing one-way links.
  • Weighted graph: Edges carry weights like costs or distances.
  • Acyclic and cyclic graphs: Graphs without or with cycles; DAGs are directed acyclic graphs.

Graph representations

  • Adjacency list: Each vertex stores a list of its adjacent vertices; efficient for sparse graphs.
  • Adjacency matrix: A 2D matrix indicating presence/weight of edges between vertex pairs; useful for dense graphs.
  • Edge list: A list of all edges, useful for certain algorithms and graph construction.

Graph traversal patterns

1. Breadth-first search (BFS)

Uses a queue: explores closest nodes first. Good for shortest path in unweighted graphs.

from collections import deque def bfs(graph, start): queue = deque([start]) visited = set([start]) while queue: node = queue.popleft() process(node) for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor)

BFS1

2. Depth-first search (DFS)

Uses recursion or a stack: explores as deep as possible before backtracking.

def dfs(graph, node, visited): visited.add(node) process(node) for neighbor in graph[node]: if neighbor not in visited: dfs(graph, neighbor, visited)

3. Cycle detection

  • Undirected: DFS with parent tracking
  • Directed: DFS with recursion stack or visited states.

4. Topological sort: Kahn's algorithm (Indegree/queue-based)

  • Compute the indegree (number of incoming edges) for every vertex.
  • Add all vertices with indegree of zero to a queue.
  • While the queue is not empty:
    • Remove a vertex from the queue, add it to the topological order.
    • For each neighbor of that vertex, decrement the neighbor's indegree by 1.
    • If any neighbor's indegree becomes zero, add it to the queue.
  • If all vertices are processed, the topological order is valid. If not, there is a cycle (ordering not possible).
from collections import defaultdict, deque def topological\_sort\_kahn(graph): indegree = defaultdict(int) for node in graph: for neighbor in graph\[node]: indegree\[neighbor] += 1

Time complexity: O(V + E), V = vertices, E = edges.

Space complexity: O(V), V = vertices.

Common pitfalls

  • Forgetting cycles in recursion.
  • Not marking nodes as visited.
  • Handling disconnected graphs (multiple components).

Graphs Cheatsheet

Practice problems

Dynamic programming (DP)

Dynamic Programming is an optimization technique used to solve problems exhibiting overlapping subproblems and optimal substructure. Instead of solving the same subproblems multiple times, DP solves each once and stores the results, typically using a table or memoization, thereby dramatically reducing time complexity from exponential to polynomial for many problems.

Learn more about dynamic programming here.

Core principles

  • Optimal substructure: The optimal solution to a problem can be constructed from optimal solutions of its subproblems.
  • Overlapping subproblems: The problem can be broken down into subproblems which are reused multiple times.

DP implementation

1. Top-down approach (memoization)

How it works:

  • Utilize recursion to solve the problem starting from the original problem down to smaller subproblems.
  • Store (memoize) solutions to subproblems in a cache to avoid recomputing.
  • Recursion break conditions correspond to base cases.
  • Intuitively easier to write as it closely follows the problem’s recursive definition.
  • May incur overhead due to recursive calls and memory used by the recursion stack.
def dp_top_down(n, memo=None): if memo is None: memo = {} # Base case if n <= 1: return n # Return memoized result if n in memo: return memo[n] # Compute and memoize memo[n] = dp_top_down(n-1, memo) + dp_top_down(n-2, memo) return memo[n]

2. Bottom-up approach (tabulation)

How it works:

  • Solve all smaller subproblems iteratively starting from base cases.
  • Build up solutions to bigger problems using a table (array).
  • Avoid recursion completely and so reduces call stack usage.
  • Often more efficient in practice.
  • Requires designing the proper order to compute subproblems so all dependencies are solved before a state.
def dp_bottom_up(n): if n <= 1: return n dp = [0] * (n+1) dp[1] = 1 for i in range(2, n+1): dp[i] = dp[i-1] + dp[i-2] return dp[n]

Time complexity

  • Recursive without memoization: Exponential O(2^n) due to repeated subproblem computations.
  • Top-down (memoization): Linear O(n) because each subproblem is solved once and cached.
  • Bottom-up (tabulation): Linear O(n) as all subproblems are solved iteratively once.

Space complexity

  • Recursive without memoization: O(n) because of the recursion call stack depth.
  • Top-down (memoization): O(n) for memo storage + O(n) recursion stack (total O(n))
  • Bottom-up (tabulation): O(n) for DP table/array.
  • Bottom-up (optimized): O(1) by storing only needed previous states (e.g., two variables for Fibonacci).

Common pitfalls

  • Not identifying overlapping subproblems: Leading to redundant computations resembling brute force recursive solutions.
  • Incorrect state definition or transition: DP heavily depends on accurate problem states and recurrence relations; mistakes lead to wrong or inefficient solutions.
  • Missing base cases: Without proper base cases, recursive memoization or iterative tabulation fails or loops infinitely.
  • Improper memoization: Forgetting to check/store results before/after recursion.
  • Excessive memory usage: Storing unnecessary states or full solution paths instead of just needed states.
  • Order of tabulation: Incorrect filling order of the DP table can break dependencies and produce wrong results.

DP Cheatsheet

Practice problems

Next Lesson