ZeroJudge 解題筆記：a229. 括號匹配問題

作者：王一哲
日期：2025年7月5日


ZeroJudge 題目連結：a229. 括號匹配問題

解題想法

我用函式遞迴枚舉所有可能的組合，但是 Python 的部分一直超時，C++ 的部分用 string 儲存字串會超時，要用字元陣列才能過關。

Python 程式碼

寫法1，用字串儲存答案，超時。

import sys

def solve(n):
    """
    輸入括號對數 n，枚舉所有合法的組合
    """
    if n == 0: return [""]  # 特例，回傳只有空字串的串列
    result = []  # 儲存組合用的串列
    def backtrack(curr, left, right):
        """
        回溯，輸入現在的字串 curr、左括號數量 left、右括號數量 right
        """
        if left == n and right == n:  # 找到新的組合，加到 result
            result.append(f"{curr}\n")
            return
        if left < n:  # 如果左括號數量不夠，回溯，加上 (
            backtrack(curr+"(", left+1, right)
        if right < left:  # 如果右括號比左括號少，回溯，加上 )
            backtrack(curr+")", left, right+1)
    ### End of backtrack ###
    backtrack("", 0, 0)  # 呼叫 backtrack
    return result

ca = 0
for line in sys.stdin:
    if not line.rstrip(): continue
    ca += 1
    if ca > 1: sys.stdout.write("\n")
    sys.stdout.write("".join(solve(int(line))))

寫法2，因為用 + 連接字串比較慢，改用串列儲存字串內容，輸出前再組成字串，但還是超時。

import sys

def solve(n):
    """
    輸入括號對數 n，枚舉所有合法的組合
    """
    if n == 0:  # 特例，換行並 return
        sys.stdout.write("\n")
        return
    curr = [""]*(2*n+1)  # 儲存字串內容用的串列，事先分配好空間
    def backtrack(pos, left, right):
        """
        回溯，輸入正在處理的索引值 pos、左括號數量 left、右括號數量 right
        """
        if left == n and right == n:  # 找到新的組合，curr 接成字串並輸出
            sys.stdout.write("".join(curr[:pos]) + "\n")
            return
        if left < n:  # 如果左括號數量不夠，回溯，加上 (
            curr[pos] = "("
            backtrack(pos+1, left+1, right)
        if right < left:  # 如果右括號比左括號少，回溯，加上 )
            curr[pos] = ")"
            backtrack(pos+1, left, right+1)
    ### End of backtrack ###
    backtrack(0, 0, 0)  # 呼叫 backtrack

ca = 0
for line in sys.stdin:
    if not line.rstrip(): continue
    ca += 1
    if ca > 1: sys.stdout.write("\n")
    solve(int(line))

C++ 程式碼

寫法1，用 string 儲存字串內容，超時。

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

void backtrack(string curr, int left, int right, int n) {
    /* 回溯，輸入現在的字串 curr、左括號數量 left、右括號數量 right、括號對數 n */
    if (left == n && right == n) {  // 找到新的組合，印出 curr 並 return
        cout << curr << "\n";
        return;
    }
    if (left < n) {  // 如果左括號數量不夠，回溯，加上 (
        backtrack(curr+"(", left+1, right, n);
    }
    if (right < left) {  // 如果右括號比左括號少，回溯，加上 )
        backtrack(curr+")", left, right+1, n);
    }
}

void solve(int n) {
    if (n == 0) return;  // 特例，直接 return
    string curr = "";  // 空字串
    backtrack(curr, 0, 0, n);  // 呼叫 backtrack
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, ca = 0;
    while(cin >> n) {
        ca++;
        if (ca > 1) cout << "\n";
        solve(n);
    }
    return 0;
}

寫法2，改用字元陣列儲存字串內容，使用時間約為 0.2 s，記憶體約為 288 kB，通過測試。

#include <iostream>
using namespace std;

void backtrack(char* curr, int pos, int left, int right, int n) {
    /* 回溯，輸入現在的字串 curr、索引值 pos、左括號數量 left、右括號數量 right、括號對數 n */
    if (left == n && right == n) {  // 找到新的組合，印出 curr 並 return
        curr[pos] = '\0';  // 加上字串結束符號
        cout << curr << "\n";
        return;
    }
    if (left < n) {  // 如果左括號數量不夠，回溯，加上 (
        curr[pos] = '(';
        backtrack(curr, pos+1, left+1, right, n);
    }
    if (right < left) {  // 如果右括號比左括號少，回溯，加上 )
        curr[pos] = ')';
        backtrack(curr, pos+1, left, right+1, n);
    }
}

void solve(int n) {
    if (n == 0) return;  // 特例，直接 return
    char* curr = new char[2*n + 1];  // 空字串，改用字元陣列
    backtrack(curr, 0, 0, 0, n);  // 呼叫 backtrack
    delete[] curr;  // 釋放記憶體
}

int main() {
    int n, ca = 0;
    while(cin >> n) {
        ca++;
        if (ca > 1) cout << "\n";
        solve(n);
    }
    return 0;
}