Calculate the N-Dimensional Cartesian product recursively

product.cpp

#include <iostream>
#include <vector>

using namespace std;
using VVI = vector<vector<int>>;


template<class T>
void recursive_product(
    const vector<vector<T>>& arrays, vector<vector<T>>& result, int idx=0
){
    if (idx == arrays.size()) {
        return;
    }
    else if (idx == 0){
        for (auto val : arrays[0]){
            result.push_back( vector<T> {val} );
        }
    } else {
        vector<vector<T>> new_result;
        for (auto x : result){  // {1}, {2}
            for (auto val : arrays[idx]){
                x.push_back(val);
                new_result.push_back(x);
                x.pop_back();
            }
        }
        result = new_result;
    }
    recursive_product(arrays, result, ++idx);
} 

/*
 * Calculate the N-Dimensional Cartesian product
 */
template<class T>
vector<vector<T>> product_nd(const vector<vector<T>>& arrays){
    vector<vector<T>> result;
    recursive_product(arrays, result);
    return result;
}

int main() {
    VVI a {
        vector<int>{1, 2, 3},
        vector<int>{4, 5, 6},
        vector<int>{7, 8, 9},
    };
    VVI result = product_nd<int>(a);
    if (true) {
        for (auto arr : result){
            for (auto val : arr){
                cout << val << ", ";
            }
            cout << endl;
        }
    }
    return 0;
}