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

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

Constraints:

• n == graph.length
• 2 <= n <= 15
• 0 <= graph[i][j] < n
• graph[i][j] != i (i.e., there will be no self-loops).
• The input graph is guaranteed to be a DAG.

所有可能的路径。

这个题是一道比较典型的把回溯backtracking应用到图的题目。既然是是找all possible paths，所以会想到类似DFS/backtracking的思路。面试遇到了不能做不出来啊。。。(＃￣～￣＃)

这个题给的是array of array，题意不是很直观，我这里解释一下。比如题目中给的例子，意思是0可以连到1,2；1可以连接到3；2可以连接到3；3不能连到任何点（其实3也就是路径的终点了）。base case是当前遍历到graph里面的最后一个节点，则把当前list的结果加入结果集；其他部分则是跟其他经典的回溯类型的题没有区别。

时间O(n)

空间O(n)

Java实现

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        path.add(0);
        dfs(graph, 0, res, path);
        return res;
    }
    
    private void dfs(int[][] graph, int index, List<List<Integer>> res, List<Integer> path) {
        // base case
        if (index == graph.length - 1) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int next : graph[index]) {
            path.add(next);
            dfs(graph, next, res, path);
            path.remove(path.size() - 1);
        }
    }
}

LeetCode 题目总结