Leetcode 797. All Paths From Source to Target

797. All Paths From Source to Target

DFS the whole graph can help us find all the paths from the source to the target. Since it is a directed graph without a cycle, we can do the DFS safely.

Reference Code

class Solution {
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<vector<int>> ret;
        const int n = graph.size();
        stack<pair<int, vector<int>>> open_list;
        open_list.emplace(0, vector<int>{});
        while (!open_list.empty())
        {
            auto node = open_list.top(); open_list.pop();
            auto this_ret = node.second;
            this_ret.push_back(node.first);
            if (node.first == n-1)
            {
                ret.push_back(this_ret);
                continue;
            }
            for (auto j : graph[node.first])
            {
                open_list.emplace(j, this_ret);
            }
        }
        return ret;
    }
};

We can also use backtracking to solve the problem.

class Solution {
public:
    void backtrack(vector<vector<int>>& graph, vector<vector<int>>& paths, vector<int>& path, int curr, int dst)
    {
        if (curr == dst)
        {
            paths.push_back(path);
            return;
        }
        else
        {
            for (auto next : graph[curr])
            {
                path.push_back(next);
                backtrack(graph, paths, path, next, dst);
                path.pop_back();
            }
        }
    }
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<vector<int>> ret;
        vector<int> path = {0};
        const int n = graph.size();
        backtrack(graph, ret, path, 0, n-1);
        return ret;
    }
};