797. All Paths From Source to Target

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

回溯。DFS搜索所有的路径。
当搜索到最后一个位置时，保存动态数组并返回。（此处需要深拷贝数组。）
回到上一层，取走动态数组的最后一个节点。

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> ret = new LinkedList<>();
        dfs(ret, new ArrayList<>(), graph, 0);
        return ret;
    }
    
    private void dfs(List<List<Integer>> ret, List<Integer> arr, int[][] graph, int i){
        if( i == graph.length - 1){
            arr.add(i);
            ret.add(new ArrayList(arr));
            return;
        }
        arr.add(i);
        for( int j : graph[i] ){
            dfs(ret, arr, graph, j);
            arr.remove(arr.size()-1);
        }
    }
}