1、思路

• 经典的DFS找路径题，用一个path数组存储当前路径，达到终点后将path路径放入结果数组res中；

• 若图中节点数目为 $v$ ，边的数目为 $e$ ，那么DFS的时间复杂度为 $O(v + e)$。

2、代码

class Solution {
public:
    void dfs(vector<vector<int>>& graph, int cur, vector<vector<int>>& res, vector<int>& path)
    {
        if (cur == (int)graph.size() - 1)   //已经到达终点
        {
            res.push_back(path);
        }
        else
        {
            for (auto next : graph[cur])    //遍历当前节点所能到达的节点
            {
                path.push_back(next);
                dfs(graph, next, res, path);
                path.pop_back();            //还原现场
            }
        }
    }

    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<vector<int>> res;
        vector<int> path;

        path.push_back(0);                  //每条路径必有初始节点
        dfs(graph, 0, res, path);

        return res;
    }
};