797_AllPathsFromSourcetoTarget - a920604a/leetcode GitHub Wiki

class Solution {
public:
    void traverse(vector<vector<int>>& graph, int cur, vector<int>& path, vector<vector<int>>& ret){
        // 添加節點至路徑
        path.push_back(cur);
        if(path.back() == graph.size()-1){
            // 抵達終點
            ret.push_back(path);
            path.pop_back();
            return;
        }
        // 遞迴每個相鄰節點
        for(int  neighbor:graph[cur]){
            traverse(graph, neighbor, path, ret);
            
        }
        
        path.pop_back();
        
    }
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        
        vector<vector<int>> ret;
        vector<int> path;
        traverse(graph, 0, path, ret);
        return ret;
    }
};

class Solution {
public:
    vector<vector<int>> ret;
    void dfs(vector<vector<int>> &graph, vector<int> &path, int start){
        
        path.push_back(start);
        if(!path.empty() && path.back() == graph.size()-1){
            ret.push_back(path);
        }
        for(auto a:graph[start]){
            dfs(graph, path, a);
        }
        path.pop_back();
    }
    
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<int> path;
        dfs(graph, path, 0);
        return ret;
        
    }
};