n对括号有多少种排列_百度知道
n对括号有多少种排列
我有更好的答案
对于n+1个符号n对括号，用S(n+1)表示匹式的个数。则S(n+1) = S(1)S(n)+S(2)S(n-1) ++S(n)S(1) 其中S(1) = S(2) = 1S(k) = S(1)S(k-1) + S(2)S(k-2) + +S(k-1)S(1)详见卡塔兰数（Catalan数）。
采纳率：92%
为您推荐：
其他类似问题
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。& 小米面试题一道：N对括号所有的合法状态
小米面试题一道：N对括号所有的合法状态
文章作者：Yx.Ac
& 文章来源：勇幸|Thinking ()
& 转载请注明，谢谢合作。
给定N对括号，输出其所有的合法的组合状态，例如，N=3，所有的合法状态为："((()))”, “(()())”, “(())()”, “()(())”, “()()()”
思路：还是深搜DFS的思路，深搜的过程关键在于记录已经用掉的左括号个数和右括号的个数，当用过的左括号个数小于右括号则非法；当二者个数和大于2N则非法；当二者个数相等且数目等于2N则为合法。
代码如下：
#include&iostream&
#define PAIR 50
char str[PAIR * 2 + 1]; // 设括号对数不超过50, str记录括号组合状态
void DFS_bracket(int n, int left_used, int right_used)
if(left_used == right_used && left_used + right_used == 2*n)
printf(&%s\n&,str);
if(left_used & right_used || left_used + right_used &= 2*n)
int index = left_used + right_
str[index] = '(';
DFS_bracket(n, left_used + 1, right_used);
str[index] = ')';
DFS_bracket(n, left_used, right_used + 1);
void main()
scanf(&%d&, &N);
DFS_bracket(N,0,0);
（全文完）
点击鼠标喂喂小老鼠吧
- 36,514 views - 34,832 views - 31,948 views - 31,701 views - 25,232 views - 24,926 views - 24,051 views - 22,226 views - 22,075 views - 20,414 views - 17,844 views - 16,474 views - 15,617 views - 14,253 views - 14,205 views - 13,874 views - 13,678 views - 13,593 views - 13,493 views - 12,692 views - 12,521 views - 12,319 views - 12,242 views - 12,240 views - 12,067 views - 11,830 views - 11,592 views - 11,522 views - 11,116 views - 11,002 views - 10,844 views - 10,436 views - 10,272 views - 9,970 views - 9,969 views - 9,676 views - 9,569 views - 9,489 views - 9,316 views - 9,271 views - 8,744 views - 8,090 views输出n对括号的所有有效(左右括号成对匹配)排列
原题：Implement an algorithm to print all valid (e.g., properly opened and closed) combinations of n-pairs of parentheses.
input: 3 (e.g., 3 pairs of parentheses)
output: ()()(), ()(()), (())(), ((()))
void PrintBracketsPairRecs(char *pBegin, char *pCur, int nCurLeft) &
& & if (nCurLeft == 1) &
& & & & { &
& & & & *pCur = '('; &
& & & & *(pCur+1) = ')'; &
& & & & printf(&%s\n&, pBegin); // exit of recursive function &
& & & & } &
& & else &
& & & & { &
& & & & // 1st way: ()********* &
& & & & *pCur = '('; &
& & & & *(pCur+1) = ')'; &
& & & & PrintBracketsPairRecs(pBegin, pCur+2, nCurLeft-1); &
& & & & // 2nd way: (*********) &
& & & & *pCur = '('; &
& & & & *(pCur + (nCurLeft)*2 - 1) = ')'; &
& & & & PrintBracketsPairRecs(pBegin, pCur+1, nCurLeft-1); &
& & & & } &
void PrintBracketsPair(int n) &
& & char *pBuffer = new char[2 * n + 1]; &
& & memset(pBuffer, 0, sizeof(char) * 2 * n + 1); &
& & PrintBracketsPairRecs(pBuffer, pBuffer, n); &
& & delete [] pB &他的最新文章
他的热门文章
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)#include &iostream&
int num=0;
//判断当前n对括号是否匹配
bool isMatch(int n,char* bracket)
int left_num=0,right_num=0;
for(int i=0;i&2*n;++i)
if(bracket[i]=='l')
left_num++;
else if(bracket[i]=='r')
right_num++;
if(left_num&right_num)
if(left_num==n && right_num==n)
void BracketMatch(int n,int i,char* bracket)
if(i==2*n)
if(isMatch(n,bracket))
bracket[i]='l';
BracketMatch(n,i+1,bracket);
bracket[i]='r';
BracketMatch(n,i+1,bracket);
int main()
char* bracket=new char[2*n];
BracketMatch(n,0,bracket);
cout &&num&&
阅读(...) 评论()}