/*
  LeetCode 797. All Paths From Source to Target
  Medium

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

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

  The graph is represented as an adjacency list: graph[i] is a list of all nodes that node
  i has a directed edge to.  Find all possible paths from node 0 (source) to node n-1
  (target) and return them in any order.  Each path should be returned as a vector of node
  indices, starting with 0 and ending with n-1.

  Example 1:

   -----      ----- 
  |  0  |--->|  1  |
  |     |    |     |
   -----      -----
     |          |
     v          v
   -----      ----- 
  |  2  |--->|  3  |
  |     |    |     |
   -----      -----
   
              node  0    1   2   3 
  Input: graph = [[1,2],[3],[3],[]]
  Output: [[0,1,3],[0,2,3]]
  Explanation: There are two paths: 0 -> 1 -> 3 and 0 -> 2 -> 3.

  Example 2:
  
           ---------------------
         /                       \
        /                         \
       /         -----           -----      
      /         |  0  |-------->|  1  |
     |          |     |         |     |                         
     |           -----           -----                          
     |            /  \            / \                         
     |           /    \          /   \                        
     |          /      \        /     \                       
      \        v        v      v       v                      
       \     -----        -----         -----                   
        \   |  4  |<-----|  3  |<------|  2  |                  
         -->|     |      |     |       |     |                  
             -----        -----         ----- 

             node    0       1     2   3   4 
  Input: graph = [[4,3,1],[3,2,4],[3],[4],[]]
  Output: [[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]
 
  Constraints:
    n == graph.length
    2 <= n <= 15
    0 <= graph[i][j] < n
    graph[i][j] != i (i.e., there will be no self-loops).
    All the elements of graph[i] are unique.
    The input graph is guaranteed to be a DAG.

    Analysis:
      - Since this is a DAG (no cycles) no need to worry about visited sets for cycles
      - Can safely use Depth First Search wuth backtracking to explore every posisble path

    Key idea:
      1. Start DFS from node 0 with a current path containing {0}.
      2. At each node, recurse on all its neighbors, adding them to the current path.
      3. When we reach the target (n-1), make a copy of the current path and add it to the result.
      4. Backtrack by popping the last node to explore other branches.

    Time complexity: In worst case (dense DAG), number of paths can be exponential → O(2^n * n)
    roughly, but with n≤15 it's acceptable (2^15 = 32k, fine for Bloomberg).
    
    Space: O(n) recursion depth + O(number of paths * n) for storing result.

    Alternative: Topological sort + Dynamic Programming, but DFS backtracking is simpler and
    sufficient.

    Complexity Analysis (Bloomberg loves this)
      Time: O(N * 2^P) where P is number of paths (worst-case exponential, but n≤15 → acceptable)
      Space: O(N) recursion stack + O(total output size)

    Follow-up questions you should be ready for:
      "What if the graph had cycles?" (add visited set)
      "Can you do it iteratively?" (yes, with stack + current path)
      "How would you optimize if we only wanted k shortest paths?"
      "Memory is tight — can you yield paths instead of storing all?"
*/

#include <bits/stdc++.h>
#include <gtest/gtest.h>

using namespace std;

void print(const string& label, vector<int>& v);
void print(const string& label, vector<vector<int>>& v);
string toString(vector<int>& v);

struct Solution
{
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        int target = int(graph.size()) - 1;
        vector<int> path{0}; // init with node 0
        vector<vector<int>> results;

        print("graph: ", graph);

        function<void(int, vector<int>&)> dfs = [&](int currNode, vector<int>& path)
        {
            cout << format("dfs currNode: {} target {}\n", currNode, target);
            if (currNode == target)
            {
                print("  currNode == target results.push_back path: ", path);
                results.push_back(vector(path));
                return;
            }
            for (int nextNode : graph[currNode])
            {
                cout << format("  path.push_back({})\n", nextNode);
                path.push_back(nextNode);
                print("  dfs: nextNode: " + to_string(nextNode) + " path: ", path);
                dfs(nextNode, path);
                cout << format("  path.pop_back {}\n", path.back());
                path.pop_back(); // backtrack
            }
        };

        dfs(0, path);
        return results;
    }
};

class Solution_xAI {
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        
        int target = int(graph.size()) - 1;
        vector<int> path{};
        vector<vector<int>> result;

        print("graph: ", graph);

        function<void(int, vector<int>&)> dfs = [&](int node, vector<int>& path)
        {
            cout << format("dfs currNode: {} target {}\n", node, target);

            cout << format("  path.push_back({})\n", node);            
            path.push_back(node);        // add current node
        
            if (node == target)
            {
                print("  node==target, results.push_back path: ", path);
                result.push_back(path);  // found a valid path - copy it
            }
            else
            {
                for (int neighbor : graph[node])
                {
                    print("  dfs: neighbor: " + to_string(neighbor) + " path: ", path);
                    dfs(neighbor, path);
                }
            }

            cout << format("  path.pop_back {}\n", path.back());            
            path.pop_back(); // backtrack
        };

        dfs(0, path);
        return result;
    }
};

int main(void)
{
    vector< tuple< vector<vector<int>>, vector<vector<int>> > > testCases = {
        // input              // output
        //   0    1   2  3
        { {{1,2},{3},{3},{}}, {{0,1,3},{0,2,3}} },

        //     0       1     2   3   4
        { {{{4,3,1},{3,2,4},{3},{4},{}}}, {{{0,4},{0,3,4},{0,1,3,4},{0,1,2,3,4},{0,1,4}}}},
    };

    for (auto tc: testCases)
    {
        Solution s;
        cout << "Solution\n";        
        vector<vector<int>> input = get<0>(tc);
        vector<vector<int>> expected = get<1>(tc);        
        vector<vector<int>> result = s.allPathsSourceTarget(input);

        print("result: ", result);
        EXPECT_EQ(expected, result);

        cout << "-----------------------\n";
    }
}

void print(const string& label, vector<int>& v)
{
    string s(label + " [");
    for (auto& i: v) s += to_string(i) + ",";
    s += "] ";
    cout << s << endl;
}

string toString(vector<int>& v)
{
    string s("[");
    for (auto& i: v) s += to_string(i) + ",";
    s += "]";
    return s;    
}

void print(const string& label, vector<vector<int>>& v)
{
    cout << label <<": [";
    for (size_t i = 0; i < v.size(); i++)
    {
        cout << "[";
        for (size_t j = 0; j < v.at(i).size(); j++)
        {
            cout << v.at(i).at(j) << ",";
        }
        cout << "]";
    }
    cout << "]\n";
}