797. All Paths From Source to Target 求所有路径

 1class Solution {
 2    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
 3        List<Integer> list = new ArrayList<>();
 4        List<List<Integer>> result = new ArrayList<>();
 5        dfs(graph, new boolean[graph.length], 0, list, result);
 6        return result;
 7    }
 8
 9    // DFS。visited: 标记每一行是否访问过
10    public void dfs(int[][] graph, boolean[] visited, int cur, List<Integer> list, List<List<Integer>> result){
11        if (cur > graph.length) return;
12        list.add(cur); // 小于等于的，加入list
13        if (cur == graph.length - 1){ // 路径的长度等于二维数组的长度-1
14            result.add(new ArrayList<Integer>(list));
15            return; // 找到了就返回
16        }
17        visited[cur] = true; // 还没结束，则设置为已访问过
18        for (int v : graph[cur]){ // 遍历
19            if (!visited[v]){
20                dfs(graph, visited, v, list, result); // 递归
21                list.remove(list.size() - 1); // 删掉最后加入的，回溯的关键
22            }
23        }
24        visited[cur] = false; // 归位为未访问，这个不要忘了！
25    }