What pattern does All Paths From Source to Target use?

The Pattern: DFS (Stateful Exploration with Backtracking) The Heuristic: When enumerating all paths in a DAG, use DFS to explore each path fully, and backtrack by undoing the last step after recursion returns to restore state for alternative explorations.

All Paths From Source to Target

Q: How do you solve All Paths From Source to Target?

Implement a recursive DFS starting from node 0, maintaining the current path. When the target node is reached, append a copy of the path to the results. For each neighbor, append it to the path, recurse, then remove it (backtrack). This approach enumerates all paths efficiently and correctly.

Q: What is the time complexity of All Paths From Source to Target?

O(2^n * n). In the worst case, the number of paths can be exponential in the number of nodes, and each path can be up to length n. The algorithm explores all paths, copying each to the result.

Problem

Given a directed acyclic graph (DAG) represented as an adjacency list, return all possible paths from node 0 to node n-1, where n is the number of nodes in the graph.

2 ≤ graph.length ≤ 15
0 ≤ graph[i][j] < graph.length
The graph is guaranteed to be acyclic.

Example

Input: graph = [[1,2],[3],[3],[]]

Output: [[0,1,3],[0,2,3]]

Starting at node 0, the algorithm explores neighbors 1 and 2. From 1, it moves to 3, reaching the target and recording path [0,1,3]. From 2, it also moves to 3, recording path [0,2,3]. The DFS explores all paths exhaustively, backtracking after each complete path is found to explore alternative routes.

Approach

Straightforward Solution

A brute-force approach would attempt to generate all possible sequences of nodes, but without pruning or structure, this could be inefficient and complex to implement.

Core Observation

The problem requires enumerating all paths from a start node to an end node in a DAG. This naturally models a stateful exploration where each path is a sequence of nodes, and the graph's acyclic property guarantees no infinite loops.

Path to Optimal

Recognizing the graph is acyclic allows the use of Depth-First Search (DFS) with backtracking to systematically explore all paths. DFS explores each path fully before backtracking, ensuring all paths are found without revisiting nodes in cycles. The backtracking step restores the path state after exploring each neighbor, enabling exploration of alternative paths.

Optimal Approach

Implement a recursive DFS starting from node 0, maintaining the current path. When the target node is reached, append a copy of the path to the results. For each neighbor, append it to the path, recurse, then remove it (backtrack). This approach enumerates all paths efficiently and correctly.

Time

O(2^n * n)

In the worst case, the number of paths can be exponential in the number of nodes, and each path can be up to length n. The algorithm explores all paths, copying each to the result.

Space

O(n)

The recursion stack and path list use O(n) space, where n is the number of nodes. The output space is not counted as auxiliary space.

Solution

1class Solution:
  def allPathsSourceTarget(self, graph: list[list[int]]) -> list[list[int]]:
      target = len(graph) - 1
      res = []
5
      def dfs(node, path):
          if node == target:
              res.append(path[:])
              return
10
          for nei in graph[node]:
              path.append(nei)
              dfs(nei, path)
              path.pop()
15
      dfs(0, [0])
      return res

Step-by-Step Solution

1

Initialize Target Node and Result Container

3target = len(graph) - 1
4res = []

Objective

To define the target node index and prepare a list to collect all valid paths.

Key Insight

Identifying the target node upfront simplifies the base case check in DFS. The result list accumulates all complete paths found during traversal, enabling a clean separation between exploration and storage.

Interview Quick-Check

Core Logic

Defining the target as `len(graph) - 1` allows the DFS to know when a path is complete.

State & Boundaries

The result list must be initialized before DFS to collect all paths found.

2

Explore All Paths Recursively Using DFS with Backtracking

6def dfs(node, path):
  if node == target:
      res.append(path[:])
      return
  for nei in graph[node]:
      path.append(nei)
      dfs(nei, path)
      path.pop()

Objective

To recursively traverse the graph from the current node, building paths and backtracking after exploring each neighbor.

Key Insight

DFS explores each path fully by appending neighbors to the current path and recursing. When the target is reached, the current path is copied and saved. Backtracking by popping the last node after recursion restores the path state, enabling exploration of alternative neighbors without interference.

Interview Quick-Check

Core Logic

DFS with backtracking systematically explores all paths by extending the path with neighbors, recursing, and then undoing the extension to explore other branches.

State & Boundaries

The base case is when the current node equals the target, at which point the current path is a complete valid path.

Common Pitfalls & Bugs

Failing to backtrack (pop the last node) after recursion leads to incorrect paths that include nodes from previous branches.

3

Start DFS from Source Node and Return All Paths

16dfs(0, [0])
17return res

Objective

To initiate the DFS traversal from node 0 with the initial path and return the collected paths after exploration.

Key Insight

Starting DFS with the initial path containing only the source node sets the foundation for path building. Returning the result after DFS completes provides the full set of paths from source to target.

Interview Quick-Check

Core Logic

The initial DFS call seeds the recursion with the source node and an initial path.

State & Boundaries

Returning the result after DFS completes ensures all paths have been explored and collected.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 8 Critical

res.append(path[:])

Append a copy of the current path to the result list.

Copying the path is essential because the path list is mutable and will be modified during backtracking; storing a copy preserves the current valid path.

Line 14 Critical

path.pop()

Remove the last node from the path to backtrack after recursion.

Backtracking restores the path state to explore alternative neighbors without interference from previous recursive calls, which is critical for correctness.

Line 7 Critical

if node == target:

Check if the current node is the target node.

This base case identifies when a complete path has been found and triggers storing the path.

Line 13 Critical

dfs(nei, path)

Recursively call DFS on the neighbor node with the updated path.

This recursive call explores all paths starting from the neighbor, enabling depth-first traversal of the graph.

Line 9 Core

return

Return from the DFS call after recording a complete path.

Returning prevents further exploration from the target node, correctly terminating this path's recursion branch.

Line 12 Core

path.append(nei)

Add the neighbor node to the current path before recursion.

Extending the path with the neighbor represents moving forward in the graph and is necessary for building complete paths.

Line 16 Core

dfs(0, [0])

Start DFS traversal from the source node with the initial path containing only node 0.

Seeding the recursion with the source node and initial path sets the foundation for exploring all paths from source to target.

Line 3 Core

target = len(graph) - 1

Calculate the target node index as the last node in the graph.

Defining the target node upfront simplifies the base case check in the DFS recursion, enabling a clear stopping condition.

Line 6 Core

def dfs(node, path):

Define the recursive DFS function that explores paths from the current node.

Encapsulating the traversal logic in a recursive function allows systematic exploration of all paths with stateful path tracking.

Line 11 Core

for nei in graph[node]:

Iterate over all neighbors of the current node.

Exploring each neighbor is necessary to traverse all possible paths from the current node.

Line 17 Core

return res

Return the list of all paths found from source to target.

Returning the accumulated results after DFS completes provides the final answer to the problem.

Line 4 Standard

res = []

Initialize an empty list to store all valid paths from source to target.

This list accumulates all complete paths found during DFS, separating exploration from result storage.

Test Your Understanding

Why is backtracking (removing the last node from the path after recursion) essential in this DFS approach?

Backtracking restores the path state after exploring a neighbor, ensuring that subsequent recursive calls explore alternative paths correctly without carrying over nodes from previous paths.

Don't just read it. Drill it.

Reconstruct All Paths From Source to Target from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the All Paths From Source to Target drill

or drill a free problem

1	`class Solution:`
2	`def allPathsSourceTarget(self, graph: list[list[int]]) -> list[list[int]]:`
3	`target = len(graph) - 1`
4	`res = []`
5
6	`def dfs(node, path):`
7	`if node == target:`
8	`res.append(path[:])`
9	`return`
10
11	`for nei in graph[node]:`
12	`path.append(nei)`
13	`dfs(nei, path)`
14	`path.pop()`
15
16	`dfs(0, [0])`
17	`return res`

6	`def dfs(node, path):`
7	`if node == target:`
8	`res.append(path[:])`
9	`return`
11	`for nei in graph[node]:`
12	`path.append(nei)`
13	`dfs(nei, path)`
14	`path.pop()`

Problem

Example

Approach

Solution

Step-by-Step Solution

Initialize Target Node and Result Container

Explore All Paths Recursively Using DFS with Backtracking

Start DFS from Source Node and Return All Paths

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.