a229

輸入說明 ：

輸入一個正整數 N ， 1 =< N <= 13 。 N 代表有幾組括號要匹配

N = 1 代表 一組括號 ()

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

輸出說明 ：

輸出 N 組括號的所有合法匹配組合
輸出方式請見範例

這題,因為我還沒有完全掌握DFS所以,是把Morris大的這篇,看懂之後再照寫一次,DFS就是深度優先搜尋,這題的深度優先,看範例輸入就是要左大括弧最多的先,再來左大括弧第二多的先輸出,一直到左大括弧輸出一個馬上就換右大括弧

ex: n=3

((()))

(()())

(())()

()(())

()()()

有五種輸出

第一個是左大括弧輸出3個到極限了,換右大括弧

第二個和第三個是左大括弧輸出2個換右大括弧,這時候可以連續輸出兩個右大括弧也可以輸出一個右大括弧,只輸出一個的要排再前面,剩下類推。

Morris大的寫法,先看核心程式碼

void DFS(int r, int l, char *s)
{
    if(r== n)
    {
        puts(s-2*n);
        return;
    }

    if(l < n)
        *s = '(' ,  DFS( r, l+1, s+1);

    if(l> r)
        *s = ')' ,  DFS(r+1, l, s+1);
}

假如右大括弧跟n一樣大的時候停止,把答案印出來,用puts(s-2*n)的原因是,每次我要印的答案長度都會是2n個，

然後下面的遞迴我每都一個答案就會把指標往前移動一格，所以每次做完我都會移動2n個,

我要用puts函式印出來的時候,要先把指標移到一開始的地方，puts函式是吃一個指標,然後一直印到'\0'的前一格

接著最重要的地方是 這兩個if判斷式 他們的順序不能顛導,顛導的話整個程式還是會找到全部的答案,但是輸出的結果會跟測資剛好相反,大家可以試試看

這兩個判斷式的意思是,我會先把左括號最多的可能做完，再來回到我的上一層,看可以放幾個右大括號

#include<stdio.h>
int n;
void DFS(int r, int l, char *s)
{
    if(r== n)
    {
        puts(s-2*n);
        return;
    }
    if(l < n)
        *s = '(', DFS( r, l+1, s+1);
    if(l> r)
        *s = ')', DFS(r+1, l, s+1);
}
int main()
{
    char s[100];
    while(scanf("%d", &n) == 1)
        s[2*n] = '\0', DFS( 0, 0, s), puts("");
    return 0;
}