Skip to main content
Talentd

All Paths From Source to Target - Solution & Explanation

MediumBacktrackingDepth-First SearchBreadth-First SearchGraph15 min readAsked at: Amazon, Meta, Netflix +2
Practice this problem

Problem Statement

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

 

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

 

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.

Approach Overview

Problem Overview: You are given a directed acyclic graph (DAG) represented as an adjacency list. Starting from node 0, find every possible path that ends at node n-1. Each path must follow the directed edges of the graph and the result should include all valid sequences of nodes from source to target.

The graph is guaranteed to be acyclic, which means no node will be revisited in the same path. The main challenge is enumerating every valid path efficiently without missing combinations.

Approach 1: Depth First Search (DFS) with Backtracking (Time: O(P * N), Space: O(N))

This approach performs a depth-first traversal from the source node. Maintain a path list representing the current traversal. At each node, iterate through its neighbors and recursively explore them. When the traversal reaches node n-1, copy the current path into the result list.

Backtracking is the key idea: after exploring a neighbor, remove it from the path before moving to the next option. Because the graph is a DAG, there is no need for a visited set in the recursion stack. The time complexity depends on the number of valid paths P and the maximum path length N, giving O(P * N). Recursion depth and path storage require O(N) auxiliary space.

This method is the most natural way to enumerate paths and commonly appears in problems involving Backtracking and Depth-First Search. It is typically the expected interview solution.

Approach 2: Breadth First Search (BFS) with Path Expansion (Time: O(P * N), Space: O(P * N))

The BFS strategy builds paths level by level using a queue. Each queue entry stores an entire partial path instead of a single node. Start by pushing [0] into the queue. At each step, remove the front path, look at its last node, and extend the path with every neighbor.

If the last node equals n-1, the path is complete and added to the result. Otherwise, the extended paths are pushed back into the queue for further exploration. This effectively performs a layer-by-layer traversal of all possible path prefixes.

The algorithm still explores every valid path, so the time complexity remains O(P * N). However, BFS stores many partial paths simultaneously, leading to higher memory usage of O(P * N). The approach is useful when solving similar path enumeration problems using Breadth-First Search on a Graph structure.

Recommended for interviews: DFS with backtracking is the preferred solution. It uses minimal memory, expresses the recursive structure of path exploration clearly, and is the approach most interviewers expect. BFS demonstrates strong understanding of path expansion in graphs but consumes more memory because every partial path must be stored in the queue.

Approach 1: Depth First Search (DFS) Approach

The Depth First Search (DFS) approach uses a recursive function to explore all paths from the source node to the target node by traversing each possible node in a depth-first manner. This involves exploring as far as possible along each branch before backing up.

This C solution implements a depth-first search (DFS) recursively. The function "dfs" is called with each node and adds the node to the current path. If the current node is the target node, the path is added to the result. Otherwise, the function is called recursively for each of the node's children. Memory is dynamically allocated for the paths and adjusted for recursion depth.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(2^n) - since every node could lead to every other node, creating exponential paths.
Space Complexity: O(n) - the maximum depth of the recursion, and path storage could be O(n) as well.

Try this approach in the editor →

Approach 2: Breadth First Search (BFS) Approach

The Breadth First Search (BFS) approach uses a queue to explore nodes level by level, tracking each path as it progresses. This is an iterative process that can make finding all possible paths easier to visualize compared to recursive methods like DFS.

This C solution implements Breadth First Search (BFS) using a queue to iteratively explore the graph level by level. Paths are stored in the queue and processed in FIFO order. New paths are generated for each child node, leading to either an extension to the path or storing the path if it reaches the target node.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(2^n) - Because each node may lead to different paths creating an exponential number of routes.
Space Complexity: O(2^n) - Required for holding all potential paths in the queue.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoRustJavaScriptTypeScript

Python

Java

C++

Go

Rust

JavaScript

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Depth First Search (DFS) Approach

Time Complexity: O(2^n) - since every node could lead to every other node, creating exponential paths.
Space Complexity: O(n) - the maximum depth of the recursion, and path storage could be O(n) as well.

Breadth First Search (BFS) Approach

Time Complexity: O(2^n) - Because each node may lead to different paths creating an exponential number of routes.
Space Complexity: O(2^n) - Required for holding all potential paths in the queue.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
DFS with BacktrackingO(P * N)O(N)Best general solution for enumerating all paths in a DAG. Low memory usage and preferred in interviews.
BFS with Path ExpansionO(P * N)O(P * N)Useful when exploring paths level-by-level or adapting BFS templates for path generation problems.

Video Solution

Graph Coding Question - All Paths From Source To Target (LeetCode) • AlgosWithMichael • 43,873 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is All Paths From Source to Target easy or hard?
The problem is rated Medium on LeetCode. The traversal logic is straightforward if you understand DFS and backtracking, but recognizing that every path must be enumerated—and managing the path state correctly—makes it slightly more challenging for beginners.
All Paths From Source to Target Python/Java solution
Python and Java implementations typically use DFS recursion with a list representing the current path. When the traversal reaches the target node, the path is copied into the result list. The same logic works in C++, JavaScript, and other languages with minor syntax changes.
How to solve All Paths From Source to Target in O(n)?
Solving this problem in strict O(n) time is not possible because every valid path must be generated. The optimal solutions run in O(P * N), where P is the number of paths. DFS with backtracking is the most efficient practical approach because it avoids storing many partial paths at once.
What is the best approach for All Paths From Source to Target?
Depth First Search (DFS) with backtracking is the best approach. Start from node 0, recursively explore each neighbor, and maintain a path list. When the traversal reaches node n-1, store the path. The complexity is O(P * N), where P is the number of valid paths and N is the number of nodes in the graph.
Is All Paths From Source to Target asked at Google/Amazon/Meta?
This problem represents a common graph traversal pattern frequently used in interviews at companies like Amazon, Google, and Meta. Interviewers use it to evaluate DFS, backtracking, and understanding of path enumeration in directed graphs.
What data structure is used in All Paths From Source to Target?
The core data structure is an adjacency list representing the graph. DFS solutions use recursion with a dynamic path list, while BFS solutions use a queue storing partial paths. Arrays or lists store the final set of paths.
What is the time complexity of All Paths From Source to Target?
The time complexity is O(P * N). P represents the total number of distinct paths from the source to the target, and N is the maximum length of a path. Every valid path must be constructed and copied into the result list.

Ready to solve this problem?

Practice All Paths From Source to Target with our built-in code editor and test cases.

Practice on FleetCode
Previous

Number of Increasing Paths in a Grid

Next

Number of Ways to Arrive at Destination