All Paths From Source to Target solution and explanation
Google
9 more videos on this problem
Graph Coding Question - All Paths From Source To Target (LeetCode)AlgosWithMichael · 12:39 · 43K views
Leetcode - All Paths From Source to Target (Python)Timothy H Chang · 4:32 · 9K views
ALL PATH FROM SOURCE TO TARGET | LEETCODE 797 | PYTHON BACKTRACKING DFS SOLUTIONCracking FAANG · 9:06 · 5K views
All Paths From Source to Target | Leet code 797 | Theory explained + Python codeSai Anish Malla · 9:02 · 4K views
LeetCode 797. All Paths From Source to Target Explanation and Solutionhappygirlzt · 4:55 · 4K views
All Paths From Source To Target - LeetCode 797 - JavaScriptAlgoJS · 6:58 · 1K views
Leetcode 797 All Paths From Source to TargetRen Zhang · 8:36 · 754 views
Leetcode Solution - 797 All Paths From Source to TargetJohn Leonardo · 8:46 · 748 views
Leetcode - 797 All Path From Source To Target (Medium) in Java,PythonCoding Sensei · 15:09 · 519 views
797 - All paths from source to target 🔴🔴 | DFS | Graphs | leetcodeTechBits by Vismay · 5:37 · 377 views
The 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]).
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.length2 <= n <= 150 <= graph[i][j] < ngraph[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.
from typing import List
def allPathsSourceTarget(graph: List[List[int]]) -> List[List[int]]:
def dfs(node: int, path: List[int]):
path.append(node)
if node == len(graph) - 1:
result.append(list(path))
else:
for next_node in graph[node]:
dfs(next_node, path)
path.pop()
result = []
dfs(0, [])
return resultimport java.util.ArrayList;
import java.util.List;
public class Solution {
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
List<List<Integer>> results = new ArrayList<>();
List<Integer> path = new ArrayList<>();
dfs(0, graph, path, results);
return results;
}
private void dfs(int node, int[][] graph, List<Integer> path, List<List<Integer>> results) {
path.add(node);
if (node == graph.length - 1) {
results.add(new ArrayList<>(path));
} else {
for (int next : graph[node]) {
dfs(next, graph, path, results);
}
}
path.remove(path.size() - 1);
}
}#include <vector>
using namespace std;
void dfs(int node, int n, vector<vector<int>>& graph, vector<int>& path, vector<vector<int>>& results) {
path.push_back(node);
if (node == n - 1) {
results.push_back(path);
} else {
for (int next : graph[node]) {
dfs(next, n, graph, path, results);
}
}
path.pop_back();
}
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
vector<vector<int>> results;
vector<int> path;
dfs(0, graph.size(), graph, path, results);
return results;
}var allPathsSourceTarget = function(graph) {
const result = [];
const dfs = (node, path) => {
path.push(node);
if (node === graph.length - 1) {
result.push([...path]);
} else {
for (const next of graph[node]) {
dfs(next, path);
}
}
path.pop();
};
dfs(0, []);
return result;
};#include <stdio.h>
#include <stdlib.h>
void dfs(int node, int n, int** graph, int* graphColSize, int* path, int pathLen, int** result, int* returnSize, int** returnColumnSizes) {
path[pathLen++] = node;
if (node == n - 1) {
result[*returnSize] = malloc(pathLen * sizeof(int));
for (int i = 0; i < pathLen; i++)
result[*returnSize][i] = path[i];
(*returnColumnSizes)[*returnSize] = pathLen;
(*returnSize)++;
} else {
for (int i = 0; i < graphColSize[node]; i++)
dfs(graph[node][i], n, graph, graphColSize, path, pathLen, result, returnSize, returnColumnSizes);
}
}
int** allPathsSourceTarget(int** graph, int graphSize, int* graphColSize, int* returnSize, int** returnColumnSizes) {
int** result = malloc(1000 * sizeof(int*));
*returnColumnSizes = malloc(1000 * sizeof(int));
int* path = malloc(15 * sizeof(int));
*returnSize = 0;
dfs(0, graphSize, graph, graphColSize, path, 0, result, returnSize, returnColumnSizes);
free(path);
return result;
}using System.Collections.Generic;
public class Solution {
public IList<IList<int>> AllPathsSourceTarget(int[][] graph) {
var results = new List<IList<int>>();
var path = new List<int>();
DFS(0, graph, path, results);
return results;
}
private void DFS(int node, int[][] graph, List<int> path, List<IList<int>> results) {
path.Add(node);
if (node == graph.Length - 1) {
results.Add(new List<int>(path));
} else {
foreach (var next in graph[node]) {
DFS(next, graph, path, results);
}
}
path.RemoveAt(path.Count - 1);
}
}In Python, the solution is built using the dfs function that manages recursion. Starting from node 0, the path is extended as nodes are visited. If the target node is encountered, the path is stored in the result variable.
Time Complexity: O(2^n) - due to the exponential number of paths.
Space Complexity: O(n) - Required for the recursion stack and the path list.
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.
from typing import List
from collections import deque
def allPathsSourceTarget(graph: List[List[int]]) -> List[List[int]]:
result = []
queue = deque([[0]])
while queue:
path = queue.popleft()
last_node = path[-1]
if last_node == len(graph) - 1:
result.append(path)
else:
for next_node in graph[last_node]:
queue.append(path + [next_node])
return resultimport java.util.*;
public class Solution {
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
List<List<Integer>> results = new ArrayList<>();
Queue<List<Integer>> queue = new LinkedList<>();
queue.offer(Collections.singletonList(0));
while (!queue.isEmpty()) {
List<Integer> path = queue.poll();
int lastNode = path.get(path.size() - 1);
if (lastNode == graph.length - 1) {
results.add(new ArrayList<>(path));
} else {
for (int next : graph[lastNode]) {
List<Integer> newPath = new ArrayList<>(path);
newPath.add(next);
queue.offer(newPath);
}
}
}
return results;
}
}#include <vector>
#include <queue>
using namespace std;
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
vector<vector<int>> result;
queue<vector<int>> q;
q.push({0});
while (!q.empty()) {
vector<int> path = q.front();
q.pop();
int lastNode = path.back();
if (lastNode == graph.size() - 1) {
result.push_back(path);
} else {
for (int next : graph[lastNode]) {
vector<int> newPath = path;
newPath.push_back(next);
q.push(newPath);
}
}
}
return result;
}var allPathsSourceTarget = function(graph) {
const result = [];
const queue = [[0]];
while (queue.length > 0) {
const path = queue.shift();
const lastNode = path[path.length - 1];
if (lastNode === graph.length - 1) {
result.push(path);
} else {
for (const nextNode of graph[lastNode]) {
queue.push(path.concat(nextNode));
}
}
}
return result;
};#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_NODE 15
#define MAX_PATHS 2048
int** allPathsSourceTarget(int** graph, int graphSize, int* graphColSize, int* returnSize, int** returnColumnSizes) {
int** result = malloc(MAX_PATHS * sizeof(int*));
*returnColumnSizes = malloc(MAX_PATHS * sizeof(int));
*returnSize = 0;
int queue[MAX_PATHS][MAX_NODE];
int front = 0, rear = 0;
int pathLens[MAX_PATHS];
memcpy(queue[rear], (int[]){0}, sizeof(int));
pathLens[rear++] = 1;
while (front < rear) {
int* curPath = queue[front];
int curLen = pathLens[front++];
int lastNode = curPath[curLen - 1];
if (lastNode == graphSize - 1) {
result[*returnSize] = malloc(curLen * sizeof(int));
memcpy(result[*returnSize], curPath, curLen * sizeof(int));
(*returnColumnSizes)[*returnSize] = curLen;
(*returnSize)++;
} else {
for (int i = 0; i < graphColSize[lastNode]; i++) {
memcpy(queue[rear], curPath, curLen * sizeof(int));
queue[rear][curLen] = graph[lastNode][i];
pathLens[rear++] = curLen + 1;
}
}
}
return result;
}using System.Collections.Generic;
public class Solution {
public IList<IList<int>> AllPathsSourceTarget(int[][] graph) {
var results = new List<IList<int>>();
var queue = new Queue<List<int>>();
queue.Enqueue(new List<int> {0});
while (queue.Count > 0) {
var path = queue.Dequeue();
int lastNode = path[path.Count - 1];
if (lastNode == graph.Length - 1) {
results.Add(new List<int>(path));
} else {
foreach (var next in graph[lastNode]) {
var newPath = new List<int>(path) {next};
queue.Enqueue(newPath);
}
}
}
return results;
}
}In this Python solution, a queue enables breadth-first traversal of the graph. Starting with a path containing just the source node, paths grow as nodes are explored until they either hit the target node, at which time they're stored, or continue extending with further outgoing paths.
Time Complexity: O(2^n) - Each node could lead to all others, increasing paths exponentially.
Space Complexity: O(2^n) - Storage of all potential paths as items in the queue.
Approach 3: Default Approach
function allPathsSourceTarget(graph: number[][]): number[][] {
const ans: number[][] = [];
const dfs = (path: number[]) => {
const curr = path.at(-1)!;
if (curr === graph.length - 1) {
ans.push([...path]);
return;
}
for (const v of graph[curr]) {
path.push(v);
dfs(path);
path.pop();
}
};
dfs([0]);
return ans;
}func allPathsSourceTarget(graph [][]int) [][]int {
var path []int
path = append(path, 0)
var ans [][]int
var dfs func(i int)
dfs = func(i int) {
if i == len(graph)-1 {
ans = append(ans, append([]int(nil), path...))
return
}
for _, j := range graph[i] {
path = append(path, j)
dfs(j)
path = path[:len(path)-1]
}
}
dfs(0)
return ans
}impl Solution {
fn dfs(i: usize, path: &mut Vec<i32>, res: &mut Vec<Vec<i32>>, graph: &Vec<Vec<i32>>) {
path.push(i as i32);
if i == graph.len() - 1 {
res.push(path.clone());
}
for j in graph[i].iter() {
Self::dfs(*j as usize, path, res, graph);
}
path.pop();
}
pub fn all_paths_source_target(graph: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
let mut res = Vec::new();
Self::dfs(0, &mut vec![], &mut res, &graph);
res
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Depth First Search (DFS) Approach | Time Complexity: O(2^n) - due to the exponential number of paths. |
| Breadth First Search (BFS) Approach | Time Complexity: O(2^n) - Each node could lead to all others, increasing paths exponentially. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS with Backtracking | O(P * N) | O(N) | Best general solution for enumerating all paths in a DAG. Low memory usage and preferred in interviews. |
| BFS with Path Expansion | O(P * N) | O(P * N) | Useful when exploring paths level-by-level or adapting BFS templates for path generation problems. |
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.