Code Logo

All Paths From Source to Target

Published at25 Jul 2026
Created by
DFS Medium 0 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 a list of nodes that node i can go to.

Use DFS with backtracking. Start from node 0, explore each neighbor recursively, tracking the current path. When the target node (n-1) is reached, add the current path to the result.

Time complexity depends on the number of paths. Space is O(n) for the recursion stack and path storage.

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
Recommendation Algorithm Flow for All Paths From Source to Target

Solution Approach

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

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);
    }
}