Medium
BacktrackingDepth-First SearchBreadth-First SearchGraph TheoryDirected Acyclic Graph
Updated Sep 2026

All Paths From Source to Target

Asked at Netflix

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.

Asked At

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.

Visual walkthrough for graph: 0->1, 0->2, 1->3, 2->3, 3->4 (target=4):
DFS from 0:

  • Path: [0]. Neighbors: 1, 2.
    • Go to 1. Path: [0,1]. Neighbors: 3.
      • Go to 3. Path: [0,1,3]. Neighbors: 4.
        • Go to 4. Path: [0,1,3,4]. Target! Add to result.
      • Backtrack. Path: [0,1]. No more neighbors.
    • Backtrack. Path: [0]. Go to 2. Path: [0,2]. Neighbors: 3.
      • Go to 3. Path: [0,2,3]. Neighbors: 4.
        • Go to 4. Path: [0,2,3,4]. Target! Add to result.
      • Backtrack. Path: [0,2]. No more neighbors.
        Result: [[0,1,3,4], [0,2,3,4]]
6.

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.

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

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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.

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]].