class Solution {
public List> allPathsSourceTarget(int[][] graph) {
int n = graph.length;
List> result = new ArrayList>();
if(n == 0) return result;
int[] visited = new int[n];
List path = new ArrayList();
dfs(graph, 0, result, path, visited);
return result;
}
public void dfs(int[][] graph, int v, List> res, List path, int[] visited){
visited[v] = 1;
path.add(v);
if(graph[v].length == 0){
ArrayList foundPath = new ArrayList();
foundPath.addAll(path);
res.add(foundPath);
return;
}
for(int w : graph[v]){
if(visited[w] != 1){
dfs(graph, w, res, path, visited);
visited[w] = 0;
path.remove(path.size() - 1);
}
}
}
}