Leetcode 813 Solution

This article provides solution to leetcode question 813 (all-paths-from-source-to-target)
Categories:
Tags:
Access this page by simply typing in "lcs 813" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/all-paths-from-source-to-target

Solution

class Solution {
    vector<vector<vector<int>>> c;

public:
    void findPaths(vector<vector<int>>& graph, int i) {
        if (c[i].empty() == false)
            return;

        if (graph[i].empty() == false)
        {
            for (auto neigh: graph[i])
            {
                findPaths(graph, neigh);

                for (auto path: c[neigh])
                {
                    path.push_back(i);
                    c[i].push_back(path);
                }
            }
        }
        else
            c[i].push_back({i});
    }

    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        int n = graph.size();
        c.resize(n);
        findPaths(graph, 0);

        vector<vector<int>> ans;
        for (auto path: c[0])
        {
            reverse(path.begin(), path.end());
            ans.push_back(path);
        }
        return ans;
    }
};