Given a directed acyclic graph (DAG) of n nodes labeled from 0 to n - 1, find all possible paths from node 0 to node n - 1, and return them in any order.

The graph is given as follows: graph[i] is a list of all nodes you can visit from node i (i.e., there is a directed edge from node i to node graph[i][j]).

 

Example 1:

Input: graph = [[1,2],[3],[3],[]]
Output: [[0,1,3],[0,2,3]]
Explanation: There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.

Example 2:

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]]

Example 3:

Input: graph = [[1],[]]
Output: [[0,1]]

Example 4:

Input: graph = [[1,2,3],[2],[3],[]]
Output: [[0,1,2,3],[0,2,3],[0,3]]

Example 5:

Input: graph = [[1,3],[2],[3],[]]
Output: [[0,1,2,3],[0,3]]

 1 class Solution {
 2     public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
 3         List<List<Integer>> allLists = new ArrayList<>();
 4         helper(0, graph.length - 1, graph, new HashSet<>(), allLists, new ArrayList<>());
 5         return allLists;
 6     }
 7     
 8     private void helper(int current, int target, int[][] graph, Set<Integer> visited, List<List<Integer>> allLists, List<Integer> singleList) {
 9         singleList.add(current);
10         visited.add(current);
11         if (current == target) {
12             allLists.add(new ArrayList<>(singleList));
13             visited.remove(current);
14             singleList.remove(singleList.size() - 1);
15             return;
16         }
17         
18         for (int neighbor : graph[current]) {
19             if (!visited.contains(neighbor)) {
20                 helper(neighbor, target, graph, visited, allLists, singleList);
21             }
22         }
23         visited.remove(current);
24         singleList.remove(singleList.size() - 1);
25     }
26 }

or 

 1 class Solution {
 2     public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
 3         List<List<Integer>> allLists = new ArrayList<>();
 4         helper(0, graph.length - 1, graph, new HashSet<>(), allLists, new ArrayList<>());
 5         return allLists;
 6     }
 7     
 8     private void helper(int current, int target, int[][] graph, Set<Integer> visited, List<List<Integer>> allLists, List<Integer> singleList) {
 9         singleList.add(current);
10         visited.add(current);
11         if (current == target) {
12             allLists.add(new ArrayList<>(singleList));
13         }
14         
15         for (int neighbor : graph[current]) {
16             if (!visited.contains(neighbor)) {
17                 helper(neighbor, target, graph, visited, allLists, singleList);
18             }
19         }
20         visited.remove(current);
21         singleList.remove(singleList.size() - 1);
22     }
23 }