/*
  Problem 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]).


#include <bits/stdc++.h>
using namespace std;

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

        function<void(int, vector<int>&)> backtrack = [&](int currNode, vector<int>& path)
        {
            if (currNode == target)
            {
                results.push_back(vector(path));
                return;
            }
            for (int nextNode : graph[currNode])
            {
                path.push_back(nextNode);
                backtrack(nextNode, path);
                path.pop_back();
            }
        };

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

int main(void)
{
    vector<vector<vector<int>>> testCases = {
// node:                  0     1   2  3
// vertices from node:  {{1,2},{3},{3},{}},
    };

    for (auto tc: testCases)
    {
        Solution s;
        vector<vector<int>> v = tc;
        vector<vector<int>> result = s.allPathsSourceTarget(v);
        cout << "input:\n";
        for (int i = 0; i < (int)v.size(); i++)
        {
            cout << "Node " << i << endl;
            if (v.at(i).size() == 0 ) cout << "  []" << endl;
            for (int j = 0; j < (int)v.at(i).size(); j++)
            {
                if (v.at(i).size() == 1 ) cout << "  [" << v.at(i).at(j) << "]" << endl;
                else
                {                    
                    if (j==0) cout << "  [" << v.at(i).at(j) << ",";
                    else cout << v.at(i).at(j) << "]\n";
                }
            }
            cout << endl;
        }
        
        cout << "result:\n";
        for (int i = 0; i < (int)result.size(); i++)
        {
            for (int j = 0; j < (int)result.at(i).size(); j++)
            {
                cout << result.at(i).at(j) << " ";
            }
            cout << endl;
        }
        cout << endl;

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