# 【AtCoder】Encyclopedia of Parentheses

## [題目連結](https://atcoder.jp/contests/typical90/tasks/typical90_b)

## **時間複雜度**

* $O(2^N)$

## **解題想法**

### **觀察**

要想解出這一題的話要先從合法的括號中觀察出幾個東西

1. 無論如何，只要 n 為**奇數**必定**無解**
2. 在任何時刻，左括號的數量**必定大於等於**右括號
3. 當左括號的數量等於右括號的數量時，**只能**放入左括號，否則一定不合法

### **實作**

在實作呼叫遞迴的部分要記得每 Call 完一次 Function 就要馬上歸還狀態，因為要輸出的 Sol 字串是開在全域的，所以不能說 Function 結束就不管他

## **完整程式**

/* Question : AtCoder Competitive Professional Typical 90 Questions - 002 - Encyclopedia of Parentheses（★3） */

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

#define opt ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mem(x) memset(x, 0x3F, sizeof(x));
#define pii pair<int, int>
#define pdd pair<double, double>
#define f first
#define s second

const auto dir = vector< pair<int, int> > { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
const int MAXN = 1e8 + 50;
const int Mod = 1e9 + 7;
int n;
string sol;

void generate( int l, int r ){
    if( l + r == n ){
        if( l == r ) cout << sol << "\n";
        return;
    }

    if( l == r ){
        sol.push_back('(');
        generate(l+1, r);
        sol.pop_back();
    }else{
        sol.push_back('(');
        generate(l+1, r);
        sol.pop_back();

        sol.push_back(')');
        generate(l, r+1);
        sol.pop_back();
    }
}

signed main(){
    opt;
    cin >> n;
    if( n % 2 == 0 ) generate(0, 0);
}