首页 > 代码库 > n个括号对的所有可能情况

n个括号对的所有可能情况

所有可能情况的数量为卡特兰数。故求所有可能的出栈情况与此类似。

思路:

若左括号没全插入,则插入左括号;

若已插入左括号数比已插入右括号数多,则插入右括号;

 1 #include<stdio.h> 2 void printParen(int l,int r,int n,char str[],int index) 3 { 4     if(l>n || r<0 || l<r)return;//已插入的右括号比左括号多,不合法括号对  5      6     if(l==n && r==n) printf("%s\n",str); 7     else 8     {//已插入的左括号不比已插入的右括号少  9         if(l<n)10         {//若左括号没插入完,继续插入左括号 11             str[index]=(;12             printParen(l+1,r,n,str,index+1);13         }14         if(l>r)15         {//若已插入的左括号比右括号多,插入右括号 16             str[index]=);17             printParen(l,r+1,n,str,index+1);18         }19     }20 }21 int main()22 {23     static int count=3;24     char str[2*count+1];25     str[2*count]=\0;26     printParen(0,0,count,str,0);27     return 0;28 } 

 

n个括号对的所有可能情况