797. All Paths From Source to Target

797. All Paths From Source to Target (Medium)

Given a directed, acyclic graph of N nodes.  Find all possible paths from node 0 to node N-1, and return them in any order.

The graph is given as follows:  the nodes are 0, 1, ..., graph.length - 1.  graph[i] is a list of all nodes j for which the edge (i, j) exists.

Example:
Input: [[1,2], [3], [3], []] 
Output: [[0,1,3],[0,2,3]] 
Explanation: The graph looks like this:
0--->1
|    |
v    v
2--->3
There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.

Note:

• The number of nodes in the graph will be in the range [2, 15].
• You can print different paths in any order, but you should keep the order of nodes inside one path.

Companies:
Bloomberg, Walmart Labs

Solution 1.

// OJ: https://leetcode.com/problems/all-paths-from-source-to-target/
// Author: github.com/lzl124631x
// Time: O(N * 2^N)
// Space: O(N)
class Solution {
private:
    vector<vector<int>> ans;
    unordered_set<int> seen;
    vector<int> path;
    void dfs(vector<vector<int>>& graph, int from) {
        path.push_back(from);
        if (from == graph.size() - 1) ans.push_back(path);
        else {
            seen.insert(from);
            for (int n : graph[from]) {
                if (seen.find(n) != seen.end()) continue;
                dfs(graph, n);
            }
            seen.erase(from);
        }
        path.pop_back();
    }
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        dfs(graph, 0);
        return ans;
    }
};