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

using namespace std;

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";
}    


int main(void)
{
    //                               0      1     2   3  4
    vector<vector<int>> input = {{4,3,1},{3,2,4},{3},{4},{}};
    vector<vector<int>>  out = {{0,4},{0,3,4},{0,1,3,4},{0,1,2,3,4},{0,1,4}};
    
    vector<int> path{0}; // init with 0
    vector<vector<int>> results;

    int graphSize = input.size() - 1;
    
    function<void(int, vector<int>&)> dfs = [&dfs, &results, &graphSize, &input](int currNode, vector<int>& path)
    {
        if (currNode == graphSize)
        {            
            results.push_back(vector(path));
            return;
        }
        
        for (int node: input[currNode]) // Node 0, node 1, ...
        {
            path.push_back(node);
            dfs(node, path);
            path.pop_back(); // backtrack
        }                 
    };

    dfs(0, path);

    print("results", results);
    EXPECT_EQ(results, out);
}