<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;
        vector<int> curr = {};
        
        std::set<int> mySet;
        
        backtrack(curr,ans,graph,0);
        return ans;
        
        
        
        
    }
    
    void backtrack(vector<int>& curr, vector<vector<int>>& ans, vector<vector<int>>& graph, int d){
        
      //  std::cout<<"this is what happens at the beginning of backtrack for vectCount"<<endl;
        curr.push_back(d);
        
      //  std::cout<<d<<endl;
      
        
        int vectCount = d;
        
      //  int aa = -1;
        
        //if(!curr.empty()){
        //    aa = curr.back();
      //  }
        //  std::cout<<"this is what happens at the beginning of backtrack for curr"<<endl;
       //   std::cout<<aa<<endl;
        
        //std::cout<<aa<<endl;
        
        if(!curr.empty()&&curr.back()== graph.size()-1){
            
          //  std::cout<<"I got inside the last case"<<endl;
            
          //  std::cout<<graph.size()-1<<endl;
            
            ans.push_back(curr);
            
            return;
            
        }
        
       // std::cout<<"hello my friend"<<endl;
          
        
        for(int a:graph[vectCount]){
            
           // std::cout<<"I got inside the graph loop here is the new curr"<<endl;
            
            //each vecCount represents the beginning of a curr vector
           // curr.push_back(vectCount);
            vectCount = a;
            
         //   std::cout<<curr.back()<<endl;
            
             //std::cout<<"------------------------------------------"<<endl;
            
            backtrack(curr,ans,graph,vectCount);
            curr.pop_back();
  
        }
    }
      
    
    
};


/*

// let curr represent the thing you are building
// it could be an array or a combination of variables

function backtrack(curr) {
    if (base case) {
        Increment or add to answer
        return
    }

    for (iterate over input) {
        Modify curr
        backtrack(curr)
        Undo whatever modification was done to curr
    }
}

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> curr = {};
        backtrack(curr, ans, nums);
        return ans;
    }
    
    void backtrack(vector<int>& curr, vector<vector<int>>& ans, vector<int>& nums) {
        if (curr.size() == nums.size()) {
            ans.push_back(curr);
            return;
        }
        
        for (int num: nums) {
            if (find(curr.begin(), curr.end(), num) == curr.end()) {
                curr.push_back(num);
                backtrack(curr, ans, nums);
                curr.pop_back();
            }
        }
    }
};



*/
13426