Code Logo

All Paths From Source to Target

Published at25 Jul 2026
Created by
DFS Medium 5 views
Like0

Given a directed acyclic graph (DAG) with n nodes labeled from 0 to n-1, find all possible paths from node 0 to node n-1. The graph is given as an adjacency list where graph[i] is the list of nodes that node i has an outgoing edge to.

The answer is a list of paths, and each path is a list of node labels starting with 0 and ending with n-1. The order of paths in the answer does not matter, but every distinct route must be included exactly once.

For example, with graph = [[4,3,1],[3,2,4],[3],[4],[]], the answer is [[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]. Each path follows directed edges from 0 to 4. With graph = [[1],[]], the only path is [0,1]. With graph = [[]] (a single node), the start equals the target, so the answer is [[0]].

Because the graph is acyclic, there are no cycles to worry about, so a simple depth-first traversal that records the current path is enough. You never need to track a visited set — the absence of cycles guarantees the recursion terminates.

This problem appears in routing, dependency analysis, and circuit design where you must enumerate every way to reach a target. It is a classic introduction to DFS with backtracking and to path enumeration in graphs.

Edge cases include a single-node graph (the answer is [[0]]), a graph with no paths to the target (return an empty list), and dense graphs where the number of paths grows exponentially with n.

Example Input & Output

Example 1
Input
[[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]]
Explanation

Multiple paths

Example 2
Input
[[1],[]]
Output
[[0,1]]
Explanation

Single path

Example 3
Input
[[2],[3],[1,3],[]]
Output
[[0,2,1,3],[0,2,3]]
Explanation

Two paths different routes

Example 4
Input
[[]]
Output
[[0]]
Explanation

Start is target

Example 5
Input
[[1,2],[3],[3],[]]
Output
[[0,1,3],[0,2,3]]
Explanation

Two paths

Algorithm Flow

Recommendation Algorithm Flow for All Paths From Source to Target

Solution Approach

Use depth-first search with backtracking. Start from node 0, append it to the current path, and explore each neighbor recursively. When the current node equals the target (n-1), copy the path into the result. After exploring a node, remove it from the path so sibling branches are not polluted.

function solution(graph) {
  var result = [], n = graph.length;
  function dfs(node, path) {
    path.push(node);
    if (node === n - 1) {
      result.push(path.slice());
    } else {
      for (var i = 0; i < graph[node].length; i++) {
        dfs(graph[node][i], path);
      }
    }
    path.pop();
  }
  dfs(0, []);
  return result;
}

The path.slice() makes a copy before storing it in the result, because path is mutated by backtracking. The final path.pop() undoes the current choice so the recursion can explore sibling branches correctly.

Time complexity is O(number of paths), space complexity is O(n) for the recursion stack and current path.

Best Answers

java
import java.util.*;
class Solution {
    public String solution(int[][] g){
        List<String> r=new ArrayList<>();dfs(0,g,new ArrayList<>(),r,g.length);
        return String.join(",",r);
    }
    void dfs(int u,int[][] g,List<Integer> p,List<String> r,int n){
        p.add(u);if(u==n-1){StringBuilder sb=new StringBuilder();for(int x:p){if(sb.length()>0)sb.append(",");sb.append(x);}r.add(sb.toString());}
        else for(int v:g[u])dfs(v,g,p,r,n);
        p.remove(p.size()-1);
    }
}