Skip to main content

797. All Paths From Source to Target

medium

Return every path from node 0 to node n-1 in a directed acyclic graph. Pure recursive DFS path enumeration — no revisit guard needed because the graph is a DAG.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given a directed acyclic graph (DAG) of n nodes labeled from 0 to n - 1, find all possible paths from node 0 to node n - 1 and return them in any order. The graph is given as follows: graph[i] is a list of all nodes you can visit from node i (i.e., there is a directed edge from node i to node graph[i][j]).

Constraints

  • n == graph.length
  • 2 <= n <= 15
  • 0 <= graph[i][j] < n
  • graph[i][j] != i (i.e., there will be no self-loops).
  • All the elements of graph[i] are unique.
  • The input graph is guaranteed to be a DAG.

Examples

Example 1

Input
graph = [[1,2],[3],[3],[]]
Output
[[0,1,3],[0,2,3]]

Explanation: There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.

Example 2

Input
graph = [[4,3,1],[3,2,4],[3],[4],[]]
Output
[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

DFS from node 0. Carry the current path.

Hint 2

Base case: current node == n - 1 -> snapshot path.

Hint 3

For each neighbor, append, recurse, pop.

Hint 4

No visited set needed — it's a DAG, no cycles.

Solution approach

Reveal approach

Recursive DFS with backtracking. dfs(node, path): push node onto path. If node == n - 1, snapshot path to result. Otherwise for each next in graph[node], dfs(next, path). Pop node from path. Start with dfs(0, []). Because the graph is acyclic, no visited set is needed — every recursive call descends strictly toward n - 1. Time is O(2^n * n) worst case (the total number of paths in a DAG can be exponential in n; copying each path of length up to n contributes the n factor). Space is O(n) recursion depth plus output.

Complexity

Time
O(2^n * n)
Space
O(n)

Related patterns

  • recursion
  • dfs
  • backtracking

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google

Practice these live with InterviewChamp.AI

Drill All Paths From Source to Target and Recursion problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →