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

void generateSequence(int numOpened, int numClosed, string seq, int n, vector<string>& combinations) {
    if(seq.size() == 2 * n) {
        // base case: if the size of the sequence is 2*n, so we put n opening '('
        // and n closing ')', so a valid was produced
        combinations.push_back(seq);
        return;
    }
    if(numOpened < n) {
        // put an opening '(' if the number of opened '(' < n
        generateSequence(numOpened + 1, numClosed, seq + '(', n, combinations);
    }
    if(numClosed < numOpened) {
        // put a closing ')' only if there is unmathced opened '(', i.e.,
        // the number of closed ')' is strictly less than the number of opened '('
        generateSequence(numOpened, numClosed + 1, seq + ')', n, combinations);
    }
}

vector<string> generateParentheses(int n) {
    // wrapper function
    vector<string> combinations; // an array of all valid sequences produced
    // start the sequence with 0 opening '(' and 0 closed ')' with an empty sequence "" 
    generateSequence(0, 0, "", n, combinations);
    return combinations; // return the array after filling it
}

int main() {
    
    int n = 4;
    
    vector<string> combinations = generateParentheses(n);
    // output the valid sequences produced
    cout << "For n = " << n << ", the number of valid combinations producded = " << combinations.size() << '\n';
    for(auto&combination:combinations) cout << combination << '\n';

    return 0;
}