Given a directed acyclic graph (DAG) of n nodes, find all paths from node 0 to node n-1 and return them in any order.
Input: graph = [[1,2],[3],[3],[]] → Output: [[0,1,3],[0,2,3]]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]]
Use DFS/backtracking starting from node 0. At each node, explore all neighbors recursively. When we reach node n-1, add the current path to results. After recursion, remove the last node (backtrack).
- Start DFS from node 0 with an initial path [0].
- For each neighbor of the current node, add it to path and recurse.
- When current node == n-1, add a copy of current path to results.
- After recursion returns, remove the last node from path to backtrack.
import java.util.*;
class Solution {
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
path.add(0);
dfs(graph, 0, path, result);
return result;
}
private void dfs(int[][] graph, int node, List<Integer> path, List<List<Integer>> result) {
if (node == graph.length - 1) {
result.add(new ArrayList<>(path));
return;
}
for (int next : graph[node]) {
path.add(next);
dfs(graph, next, path, result);
path.remove(path.size() - 1);
}
}
}
- Time Complexity: O(2^N * N) — exponential paths in worst case
- Space Complexity: O(N) — recursion stack depth