You are given a directed acyclic graph (DAG). The graph is represented as an adjacency list, where:

graph[i] = list of all nodes you can go to directly from node i.

Your task is to return all possible paths from node 0 (source) to node n−1 (target).

---

Understanding the Problem

Example:

graph =
[
[1,2],
[3],
[3],
[]
]

This means:

From 0 → you can go to 1 and 2
From 1 → you can go to 3
From 2 → you can go to 3
From 3 → no outgoing edges

Possible paths from 0 to 3:

[0, 1, 3]
[0, 2, 3]

Output should be:

[
[0,1,3],
[0,2,3]
]

Because the graph is a DAG (no cycles), DFS is guaranteed to terminate.

---

Approach (Explained in Simple Language)

We need to explore all paths, so Depth-First Search (DFS) with backtracking is the simplest and most natural solution.

1. Start DFS from node 0

Keep a list to maintain the current path.

2. For each node, explore all its children

Append the child to the current path and continue DFS.

3. If we reach the final node (n−1), record the current path

Make a copy of the current path and add it to the result.

4. Use backtracking to remove the last node after exploring

This ensures that paths do not interfere with each other.

5. Finally, return all stored paths

DFS ensures that all possible valid paths are discovered.

Time complexity is manageable because the graph is small and acyclic.

---

Java Code

import java.util.*;

public class AllPathsFromSourceToTarget {

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {

        List<List<Integer>> result = new ArrayList<>();
        List<Integer> currentPath = new ArrayList<>();

        currentPath.add(0);

        dfs(graph, 0, currentPath, result);

        return result;
    }

    private void dfs(int[][] graph, int node, List<Integer> currentPath,
                     List<List<Integer>> result) {

        if (node == graph.length - 1) {
            result.add(new ArrayList<>(currentPath));
            return;
        }

        for (int next : graph[node]) {

            currentPath.add(next);

            dfs(graph, next, currentPath, result);

            currentPath.remove(currentPath.size() - 1);
        }
    }

    public static void main(String[] args) {
        AllPathsFromSourceToTarget solution = new AllPathsFromSourceToTarget();
        int[][] graph = {{1,2},{3},{3},{}};
        System.out.println(solution.allPathsSourceTarget(graph));
    }
}

---

Dry Run

graph =
[
[1,2],
[3],
[3],
[]
]

Start:

currentPath = [0]
result = []

Call dfs(0)

---

DFS at node 0

graph[0] = [1, 2]

Two branches to explore.

---

Branch 1 → Go to node 1

currentPath = [0, 1]

Call dfs(1)

DFS at node 1

graph[1] = [3]

Only one child → 3

currentPath = [0,1,3]

Node 3 is the target (n−1 = 3).
Add path to result:

result = [ [0,1,3] ]

Backtrack: remove 3
currentPath = [0,1]

Backtrack further: remove 1
currentPath = [0]

---

Branch 2 → Go to node 2

currentPath = [0, 2]

Call dfs(2)

DFS at node 2

graph[2] = [3]

Only one child → 3

currentPath = [0,2,3]

Node 3 is target → store path:

result = [ [0,1,3], [0,2,3] ]

Backtrack: remove 3
currentPath = [0,2]

Backtrack: remove 2
currentPath = [0]

---

DFS Complete

Queue exhausted and all branches explored.

Final result:

[ [0,1,3], [0,2,3] ]

---

Why This Approach Works

The graph is a DAG, so DFS will never loop infinitely.
Backtracking ensures every path is independent, avoiding conflicts.

DFS naturally explores all root-to-leaf style paths, making it perfect for this problem.

Time complexity is proportional to the number of possible paths.