MediumBacktrackingDepth-First SearchBreadth-First SearchGraphDirected Acyclic GraphUpdated Sep 2026

797. All Paths From Source to Target

Asked at Netflix

Difficulty

Medium

Time

O(2^n * n)

Space

O(n)

Pattern

Backtracking

Companies

1

Problem

You are given a directed acyclic graph (DAG) with n nodes, labeled from 0 to n - 1. A DAG is a graph where every edge has a direction and you can never follow edges to get back to where you started.

The graph is given as an adjacency list: graph[i] is the list of nodes you can reach directly from node i. So there is a directed edge from i to each node in graph[i].

Return all paths that start at node 0 and end at node n - 1. A path is just the list of nodes you visit in order. Return the paths in any order you like. If no path exists, return an empty list.

Find every route from 0 to the target

graph[1,2][3][3][]0123graph[0] = [1,2] means edges 0→1 and 0→2; node 3 hasno outgoing edges.start at 00 → 1 → 30 → 2 → 3target = node 3Both routes reach node 3, so both are answers.
In this graph node 3 is the target, and there are exactly two routes from node 0 to node 3.

Constraints

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

Examples

Example 1
Inputgraph = [[1,2],[3],[3],[]]
Output[[0,1,3],[0,2,3]]
WhyFrom node 0 you can go to 1 or 2. Both 1 and 2 lead to 3, which is the target. That gives the two paths 0→1→3 and 0→2→3.
Example 2
Inputgraph = [[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]]
WhyNode 4 is the target. From 0 you can reach 4 directly, or go through 3, or go through 1 and then take one of three routes to 4. That gives five paths in total.

Asked At

1 companies
CompanyDifficulty
NetflixMediumView all Netflix questions →

How to Think About It

1

Brute force: try all possible paths using DFS. At each node, explore all unvisited neighbors. Since the graph is a DAG, you don't need cycle detection - you just avoid revisiting nodes on the current path. Worst case is O(2^n) paths.

2

Key insight: use DFS with backtracking. Maintain a current path list. At each node, add it to the path, recurse on all unvisited neighbors, then remove it (backtrack). When you reach the target node, add a copy of the path to the result.

3

Why backtracking works: you build paths incrementally and undo the last step when exploring alternatives. The path list is shared across recursive calls, so you must copy it before adding to results.

4

Optimization: since it is a DAG, you don't need a visited set for the entire DFS - just check if a node is already on the current path. But a visited set for the current path is cleaner and prevents redundant exploration.

5

Edge cases: single node (n=1, path is [0]), no path exists (return empty), multiple edges to same node.

Optimal Approach

Use DFS with backtracking starting from node 0.

  1. Maintain a current path list starting with [0].
  2. At each node, iterate through all its neighbors.
  3. For each unvisited neighbor, add it to the path and recurse.
  4. When you reach node n-1 (target), add a copy of the path to results.
  5. After exploring all neighbors, remove the current node (backtrack).

Walkthrough with graph: 0->1, 0->2, 1->3, 2->3, 3->4:

  • Start at 0. path=[0].
  • Visit 1. path=[0,1].
    • Visit 3. path=[0,1,3].
      • Visit 4. path=[0,1,3,4]. Target! Save.
    • Backtrack to [0,1]. Done.
  • Backtrack to [0]. Visit 2. path=[0,2].
    • Visit 3. path=[0,2,3].
      • Visit 4. path=[0,2,3,4]. Target! Save.
    • Backtrack to [0,2]. Done.
  • Result: [[0,1,3,4], [0,2,3,4]].

Time: O(2^n * n) - up to 2^n paths, each of length at most n. Space: O(n) recursion depth.

DFS with backtracking

path013frontbackWe walked 0 → 1 → 3. Node 3 has neighbor 4, so we pushit next.path0134frontbackNode 4 is the target, so we copy this path into theresult.path0234frontbackAfter popping back to 0 and going through 2, we findthe second path.push neighbor, recurse, popif node == n-1: save a copy of pathskip a neighbor already on the path
We grow one path at a time, save it when it hits the target, then undo the last step to try the next branch.
ComplexityTime O(2^n * n)Space O(n)There can be up to 2^n different paths and each one has length up to n, so copying them costs that much; the recursion stack and current path only need O(n) space.

What Trips People Up in Real Interviews

1

Forgetting that this is a DAG. If the graph had cycles, you would need a proper visited set. For a DAG, checking if a node is on the current path is sufficient, but a full visited set also works.

2

Not copying the path before adding to results. The path list is mutated during backtracking. You must append list(path) or path[:], not path itself.

3

Using BFS instead of DFS. BFS works but requires storing the entire path at each queue node, which uses more memory. DFS with backtracking reuses a single path list.

4

Adding the starting node 0 to the path inside the loop instead of before the loop. Initialize the path as [0] and start DFS from node 0's neighbors.

5

Not handling the edge case where n=1. If there is only one node, the path is just [0] and it is both the start and target. Return [[0]].

Solution Code

O(2^n * n) time
def allPathsSourceTarget(graph):
    n = len(graph)
    result = []

    def dfs(node, path):
        if node == n - 1:
            result.append(list(path))
            return
        for neighbor in graph[node]:
            if neighbor not in path:
                path.append(neighbor)
                dfs(neighbor, path)
                path.pop()

    dfs(0, [0])
    return result

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the All Paths From Source to Target problem?

Given a directed acyclic graph (DAG) with n nodes labeled 0 to n-1, find all possible paths from node 0 to node n-1. This is a classic backtracking problem on DAGs that tests your ability to enumerate all paths without cycles.

How do you solve All Paths From Source to Target?

The optimal approach runs in O(2^n * n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask All Paths From Source to Target?

All Paths From Source to Target is asked at Netflix. It is a medium difficulty problem.

What are common mistakes on All Paths From Source to Target?
  • Forgetting that this is a DAG. If the graph had cycles, you would need a proper visited set. For a DAG, checking if a node is on the current path is sufficient, but a full visited set also works.
  • Not copying the path before adding to results. The path list is mutated during backtracking. You must append `list(path)` or `path[:]`, not `path` itself.
  • Using BFS instead of DFS. BFS works but requires storing the entire path at each queue node, which uses more memory. DFS with backtracking reuses a single path list.
  • Adding the starting node 0 to the path inside the loop instead of before the loop. Initialize the path as [0] and start DFS from node 0's neighbors.
  • Not handling the edge case where n=1. If there is only one node, the path is just [0] and it is both the start and target. Return [[0]].