a229 - 括號匹配問題

🔗 前往 ZeroJudge 原題

題目描述

題目要求輸出所有長度為 2N 的合法括號匹配組合，其中 N 為輸入。合法括號匹配的定義是，在任何位置，左括號的數量都大於等於右括號的數量。

解題思路

本題使用遞迴回溯法 (Backtracking) 解決。dfs 函數模擬了建立括號字串的過程。

• open 記錄目前已使用的左括號數量。
• close 記錄目前已使用的右括號數量。
• now 記錄目前字串的長度。

在每次遞迴中，我們嘗試添加一個左括號或右括號。

• 如果添加左括號後，open 的數量不超過 n，則遞迴呼叫 dfs，增加 open 和 now 的值。
• 如果添加右括號後，open 的數量大於 close，則遞迴呼叫 dfs，增加 close 和 now 的值。
• 當 now 等於 2n 時，表示已經建立了一個完整的括號字串，如果滿足合法性，則輸出該字串。

複雜度分析

• 時間複雜度: O(4^n / sqrt(n))，這實際上是卡塔蘭數的計算，因為合法括號組合的數量是卡塔蘭數。
• 空間複雜度: O(n)，主要來自遞迴的堆疊空間和 paren 字串的儲存。

程式碼

#include <stdio.h>  
int n, max;
char paren[30];
void dfs(int open, int close, int now){
    if (open > n || open < close)
        return;
    if (now == max){
        puts(paren);
        return;
    }
    paren[now] = '(', dfs(open + 1, close, now + 1);
    paren[now] = ')', dfs(open, close + 1, now + 1);
}

int main(){
    while (scanf(" %d",&n)==1){
        max=n<<1;
        dfs(0, 0, 0);
        putchar('\n');
    }
    return 0;
}