<p>Given a directed acyclic graph (<strong>DAG</strong>) of <code>n</code> nodes labeled from <code>0</code> to <code>n - 1</code>, find all possible paths from node <code>0</code> to node <code>n - 1</code> and return them in <strong>any order</strong>.</p>

<p>The graph is given as follows: <code>graph[i]</code> is a list of all nodes you can visit from node <code>i</code> (i.e., there is a directed edge from node <code>i</code> to node <code>graph[i][j]</code>).</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/09/28/all_1.jpg" style="width: 242px; height: 242px;" />
<pre>
<strong>Input:</strong> graph = [[1,2],[3],[3],[]]
<strong>Output:</strong> [[0,1,3],[0,2,3]]
<strong>Explanation:</strong> There are two paths: 0 -&gt; 1 -&gt; 3 and 0 -&gt; 2 -&gt; 3.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/09/28/all_2.jpg" style="width: 423px; height: 301px;" />
<pre>
<strong>Input:</strong> graph = [[4,3,1],[3,2,4],[3],[4],[]]
<strong>Output:</strong> [[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == graph.length</code></li>
	<li><code>2 &lt;= n &lt;= 15</code></li>
	<li><code>0 &lt;= graph[i][j] &lt; n</code></li>
	<li><code>graph[i][j] != i</code> (i.e., there will be no self-loops).</li>
	<li>All the elements of <code>graph[i]</code> are <strong>unique</strong>.</li>
	<li>The input graph is <strong>guaranteed</strong> to be a <strong>DAG</strong>.</li>
</ul>

class Solution {
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<vector<int>> ans;
        // can try to find all bottleneck nodes, unavoidable nodes, a la USACO Training car obstacle course, arange all the bottleneck nodes in chronological order checkpoint from 0 to n - 1,
        // find all ways to traverse from unavoidable_x to unavoidable_y, using a bfs (guaranteed no bottlenecks between node x and y), store all ways to traverse between all pairs of adjacent unavoidable checkpoints, then run a massive builder routine to generate all total paths 
        // from 0 to n - 1
        
        // or can simply run a backtracking DFS algo, brute forcey. This is probably slower than the above unavoidable nodes detection method.
        // code it up iteratively AND recursively!!!!!!! Many interviewers like to see you be able to code both up, demonstrates that you are a flexible and comfortable programmer!
        // input is already in adjacency list form
        vector<int> stk = {0};
        vector<int> ind = {0};
        // acyclic graph, meaning that you will never double-visit a node when following the direction of the edges!
        int n = graph.size();
        while(stk.size() > 0){
            int node = stk.back();
            int idx = ind.back();
            if(node == n - 1){
                ans.push_back(stk);
                stk.pop_back();
                ind.pop_back();
                continue;
            }
            if(idx == graph[node].size()){
                stk.pop_back();
                ind.pop_back();
                continue;
            }
            int adj = graph[node][idx];
            ind[(int)ind.size() - 1]++;
            ind.push_back(0);
            stk.push_back(adj);
        }
        return ans;
    }
};
12038