a229: 括號匹配問題

出處 ： http://zerojudge.tw/ShowProblem?problemid=a229

Content ：

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

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

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

!!! 右括弧次數大於左括弧了! (()))( 為不合法匹配

Input ：

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

N 代表有幾組括號要匹配

Ex.

N = 1 代表 一組括號 ()

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

Output ：

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

輸出方式請見範例

Sample Input ：

1

2

3

4

Sample Output ：

()

(())

()()

((()))

(()())

(())()

()(())

()()()

(((())))

((()()))

((())())

((()))()

(()(()))

(()()())

(()())()

(())(())

(())()()

()((()))

()(()())

()(())()

()()(())

()()()()

Hint ：

背景知識：

2011 / 8 / 27 11 : 50 測資修正

通過時間改為 1s

Author ：

(管理：stanley17112000)

解題策略

遞迴求解。