【題解】ZeroJudge a229: 括號匹配問題

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=a229
【解題想法】遞迴找出所有合法的括號配對。

#include <iostream>
#include <cstring>
using namespace std;

int N;
string s;
//int total;

void solve(int now, int nL, int nR) {
    if (now == 2 * N) {
    	//total++;
        cout << s << "\n";
        return;
    }
    if (nL < N) {
        s[now] = '(';
        solve(now+1, nL+1, nR);
    }
    if (nR < nL) {
        s[now] = ')';
        solve(now+1, nL, nR+1);
    }
}

int main() {
    bool first = true;
    
    while (cin >> N) {
        s = "";
        for (int i = 0; i < 2*N; i++){
            s += " "; //placeholder
        }
        
        if (first) first = false;
        else cout << "\n"; // a blank line between test cases
        //total = 0;
        solve(0, 0, 0);
        //cout << N << " : " << total << "\n";
    }
    return 0;
}
分享本文 Share with friends