Try   HackMD

【AtCoder】Encyclopedia of Parentheses

題目連結

時間複雜度

  • O(2N)

解題想法

觀察

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

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