a229: 括號匹配問題
Tags : 窮舉
Accepted rate : 944人/1114人 ( 85% ) [非即時]
評分方式:
Tolerant

最近更新 : 2011-08-27 11:50

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
()
 
(())
()()
 
((()))
(()())
(())()
()(())
()()()

(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1K
Hint :

2011 / 8 / 27   11 : 50 測資修正
通過時間改為 1s  
Tags:
窮舉
出處:
名題精選百則 [管理者:
stanley17112000 (Stanley)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」