代码随想录 797. 所有可能的路径

题目
给你一个有 n 个节点的有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）
graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。

示例 1：
在这里插入图片描述
输入：graph = [[1,2],[3],[3],[]]
输出：[[0,1,3],[0,2,3]]
解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3
示例 2：

输入：graph = [[4,3,1],[3,2,4],[3],[4],[]]
输出：[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]
提示：
n == graph.length
2 <= n <= 15
0 <= graph[i][j] < n
graph[i][j] != i（即不存在自环）
graph[i] 中的所有元素互不相同
保证输入为有向无环图（DAG）

解题思路
本题和257. 二叉树的所有路径类似，找出所有路径适合用回溯算法，也即深度优先搜索（DFS）。用path表示单条路径，用result表示路径的集合，定义回溯的形式为void dfs(vector<vector> graph,int x)，graph为图，x为当前节点所在的位置。如果x为graph的最后一个节点，则说明找出了所有路径。单层逻辑里用for横向遍历当前点x能到达的节点，用递归遍历纵向遍历每层节点。

代码实现

class Solution {
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        path.push_back(0);
        dfs(graph,0);
        return result;
    }

private:
    vector<vector<int>> result;
    vector<int> path;
    void dfs(vector<vector<int>> graph, int x) {
        if (x == graph.size()-1) {
            result.push_back(path);
            return;
        }

        for (int i=0;i<graph[x].size();i++) {
            path.push_back(graph[x][i]);
            dfs(graph,graph[x][i]);
            path.pop_back();
        }
    }
};