a229. 括號匹配問題
最近更新 : 2011-08-25 21:05
內容 ：
最近要開學了! ( ~~~ 跟題目沒有什麼關係 ) ><
請寫一個程式把所有合法括號匹配方式列出來!
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 代表有兩組括號 ()()
輸出說明
：
輸出 N 組括號的所有合法匹配組合
輸出方式請見範例
範例輸入 ：
1 2 3 4
範例輸出 ：
() (()) ()() ((())) (()()) (())() ()(()) ()()() (((()))) ((()())) ((())()) ((()))() (()(())) (()()()) (()())() (())(()) (())()() ()((())) ()(()()) ()(())() ()()(()) ()()()()
提示
：
出處
：
/**********************************************************************************/
/* Problem: a229 "括號匹配問題" from C++ 名題百則 */
/* Language: C */
/* Result: AC (128ms, 176KB) on ZeroJudge */
/* Author: morris1028 at 2011-08-26 19:50:58 */
/**********************************************************************************/
#include<stdio.h>
int n;
void DFS(int index, int r, int l, char *s) {
if(l == n) {
puts(s-2*n);
return;
}
if(r < n)
*s = '(', DFS(index+1, r+1, l, s+1);
if(r > l)
*s = ')', DFS(index+1, r, l+1, s+1);
}
main() {
char s[100];
while(scanf("%d", &n) == 1)
s[2*n] = '\0', DFS(0, 0, 0, s), puts("");
return 0;
}
上一篇：a219. 限制排列
下一篇：d739. 最少路径覆盖
hihihihihihihihi 你好厉害哦 可是我看不懂
12326544259364681321