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.

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 — DFS

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

Preview

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…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

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…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

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

Python

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

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

3

Start DFS from Source Node and Return All Paths

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

2 more steps with full analysis available on Pro.

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.

Full line-by-line criticality + rationale for all 12 lines available on Pro.

Test Your Understanding

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

See the answer with Pro.

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`