22.cpp

/**
 *    author:   vulkan
 *    created:  02.08.2021 06:07:12 PM
**/
#include <bits/stdc++.h>

using namespace std;

void _generateParenthesis(int n, vector<string> &ans, int bal, string curr) {
    if (n == 0 and bal == 0) {
        ans.push_back(curr);
        return;
    }

    if (n < 0 or bal < 0) {
        return;
    }

    _generateParenthesis(n - 1, ans, bal + 1, curr + "(");
    _generateParenthesis(n - 1, ans, bal - 1, curr + ")");
}

vector<string> generateParenthesis(int n) {
    vector<string> ans;
    _generateParenthesis(2 * n, ans, 0, "");
    return ans;
}

int main(int argc, char const *argv[]) {
    int n;
    cin >> n;
    vector<string> ans = generateParenthesis(n);
    for (string x : ans) {
        cout << x << endl;
    }

    return 0;
}