All Paths From Source to Target

Medium
446.

All Paths From Source to Target

All Paths From Source to Target is a medium coding problem on depth-first search, breadth-first search and graph, asked in Amazon, Google and Meta interviews.

You are given a directed acyclic graph of n nodes labelled 0 through n - 1, as an adjacency list where graph[i] lists the nodes reachable in one step from i.

Return every path from node 0 to node n - 1, in the order a depth-first search that follows each adjacency list left to right would find them.

Example 1

Input
graph = [[1,2],[3],[3],[]]
Output
[[0,1,3],[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]]

Example 3

Input
graph = [[]]
Output
[[0]]

Constraints

  • 1 <= graph.length <= 12
  • The graph is a DAG: every edge goes from a lower index to a higher one, except that node 0 may be a target of nothing.
  • The total output stays small.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} graph
 * @return {number[][]}
 */
var allPathsSourceTarget = function(graph) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

All Paths From Source to Target — Problem & Solution

All Paths From Source to Target solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

All Paths From Source to Target is a medium coding problem on depth-first search, breadth-first search and graph, asked in Amazon, Google and Meta interviews.

Problem statement

You are given a directed acyclic graph of n nodes labelled 0 through n - 1, as an adjacency list where graph[i] lists the nodes reachable in one step from i.

Return every path from node 0 to node n - 1, in the order a depth-first search that follows each adjacency list left to right would find them.

Example 1

Input: graph = [[1,2],[3],[3],[]]
Output: [[0,1,3],[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]]

Example 3

Input: graph = [[]]
Output: [[0]]

Constraints

  • 1 <= graph.length <= 12
  • The graph is a DAG: every edge goes from a lower index to a higher one, except that node 0 may be a target of nothing.
  • The total output stays small.

Hints for All Paths From Source to Target

  1. Hint 1

    Depth-first search from node 0, carrying the path built so far.

  2. Hint 2

    When you reach the last node, record a copy of the path — not the live array.

  3. Hint 3

    Because the graph is acyclic you never need a visited set; just undo the last step when you return.

How to solve All Paths From Source to Target

DFS from node 0 carrying the current path; record a copy whenever the target is reached and pop on the way back.

Approach

  1. Start path = [0].
  2. At node, if it is the target, append list(path); else for each successor push it, recurse, pop.

Why it works

The graph is acyclic, so every simple path is found without a visited set, and following adjacency lists in order yields the required output order.

Complexity

  • Time — O(2^n · n) in the worst case (number of paths)
  • Space — O(n) recursion plus the output

Pitfalls

  • Appending the live path list instead of a copy makes every recorded path alias the same object.

Reference solution

Python

def allPathsSourceTarget(graph):
    target = len(graph) - 1
    out = []
    path = [0]

    def walk(node):
        if node == target:
            out.append(list(path))
            return
        for nxt in graph[node]:
            path.append(nxt)
            walk(nxt)
            path.pop()

    walk(0)
    return out

Java

private static void walkPaths(int[][] graph, int node, List<Integer> path, List<int[]> out) {
    if (node == graph.length - 1) {
        int[] copy = new int[path.size()];
        for (int i = 0; i < path.size(); i++) copy[i] = path.get(i);
        out.add(copy);
        return;
    }
    for (int next : graph[node]) {
        path.add(next);
        walkPaths(graph, next, path, out);
        path.remove(path.size() - 1);
    }
}

public static int[][] allPathsSourceTarget(int[][] graph) {
    List<int[]> out = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    path.add(0);
    walkPaths(graph, 0, path, out);
    return out.toArray(new int[0][]);
}

C++

static void walkPaths(vector<vector<int>>& graph, int node, vector<int>& path, vector<vector<int>>& out) {
    if (node == (int) graph.size() - 1) {
        out.push_back(path);
        return;
    }
    for (int next : graph[node]) {
        path.push_back(next);
        walkPaths(graph, next, path, out);
        path.pop_back();
    }
}

vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
    vector<vector<int>> out;
    vector<int> path;
    path.push_back(0);
    walkPaths(graph, 0, path, out);
    return out;
}

JavaScript

var allPathsSourceTarget = function(graph) {
    const target = graph.length - 1;
    const out = [];
    const path = [0];
    const walk = function(node) {
        if (node === target) {
            out.push(path.slice());
            return;
        }
        for (let i = 0; i < graph[node].length; i++) {
            path.push(graph[node][i]);
            walk(graph[node][i]);
            path.pop();
        }
    };
    walk(0);
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)