a229: 括號匹配問題

內容

最近要開學了! ( ~ 跟題目沒有什麼關係 ) ><

請寫一個程式把所有合法括號匹配方式列出來!

Ex. (())  ,  ((()())) , ()((()))  是合法的匹配方式

    )( , (()))(  , ()(()(  是不合法的匹配方式

    合法匹配的括號 ， 從答案列的開頭到答案列某一點，左括弧次數永遠大於等於右括弧!


    Ex. 合法匹配   ((()()))

    字串 (        左括弧 : 1  >=   右括弧 : 0
    字串 ((        左括弧 : 2  >=   右括弧 : 0
    字串 (((        左括弧 : 3  >=   右括弧 : 0
    字串 ((()        左括弧 : 3  >=   右括弧 : 1
    字串 ((()(        左括弧 : 4  >=   右括弧 : 1
    字串 ((()()        左括弧 : 4  >=   右括弧 : 2
    字串 ((()())        左括弧 : 4  >=   右括弧 : 3
    字串 ((()()))        左括弧 : 4  >=   右括弧 : 4



    Ex. 不合法匹配    (()))(

    字串 (        左括弧 : 1  >=   右括弧 : 0
    字串 ((        左括弧 : 2  >=   右括弧 : 0
    字串 (()        左括弧 : 2  >=   右括弧 : 1
    字串 (())        左括弧 : 2  >=   右括弧 : 2
    字串 (()))        左括弧 : 2  <=   右括弧 : 3
        !!! 右括弧次數大於左括弧了!  (()))( 為不合法匹配

輸入

輸入一個正整數 N ， 1 =< N <= 13 。

N 代表有幾組括號要匹配

Ex.
    N = 1 代表 一組括號 ()

    N = 2 代表有兩組括號  ()()

1
2
3
4

輸出

輸出 N 組括號的所有合法匹配組合

輸出方式請見範例

()

(())
()()

((()))
(()())
(())()
()(())
()()()

(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()

解題思路

標準的遞迴題目，先用 dfs 列舉出所有可能，然後略過不符合的解

而會產生不符合的解有兩種情況

1. 放入輸出字串的左括弧數 > 目標括弧組數 (這樣如果要產生正確解一定會多一組)

2. 放入輸出字串的右括弧數 > 放入輸出字串的左括弧數 (當前字串不正確，且後面不管放再多左括弧都不能修正這個問題)

所以當產生以上兩種情況時，就可以直接 return 掉剪枝，又因為所有可能產生不符合的解的情況都被剪枝剪掉了，所以每次輸出必為正確解，就不用再做額外的判斷。

完整程式碼

AC (95ms, 64KB)

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