Given a directed, acyclic graph ofNnodes. Find all possible paths from node0to nodeN-1, and return them in any order.

The graph is given as follows: the nodes are 0, 1, ..., graph.length - 1. graph[i] is a list of all nodes j for which the edge (i, j) exists.

Example:
Input:
 [[1,2], [3], [3], []] 

Output:
 [[0,1,3],[0,2,3]] 

Explanation:
 The graph looks like this:
0---
>
1
|    |
v    v
2---
>
3
There are two paths: 0 -
>
 1 -
>
 3 and 0 -
>
 2 -
>
 3.

Note:

• The number of nodes in the graph will be in the range [2, 15] .
• You can print different paths in any order, but you should keep the order of nodes inside one path.

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> ans = new ArrayList<>();
        if (graph == null || graph.length == 0) return ans;

        int len = graph.length;
        Set<Integer> visited = new HashSet<>();
        List<Integer> path = new ArrayList<>();
        path.add(0);
        visited.add(0);
        dfs(len, 0, visited, graph, path, ans);

        return ans;
    }

    private void dfs(int len, int cur, Set<Integer> visited, int[][] graph, List<Integer> path, List<List<Integer>> ans){
        if (cur == len - 1){
            ans.add(new ArrayList<>(path));
            return;
        }

        for (int nei : graph[cur]){
            if (visited.contains(nei)) continue;

            visited.add(nei);
            path.add(nei);
            dfs(len, nei, visited, graph, path, ans);
            visited.remove(nei);
            path.remove(path.size() - 1);
        }
    }
}