本文共 1163 字，大约阅读时间需要 3 分钟。

Implement an algorithm to print all valid (e. g. , properly opened and closed) combinations of n-pairs of parentheses. EXAMPLE: input: 3 (e. g. , 3 pairs of parentheses)

output: ()()(), ()(()), (())(), ((()))，(()())

两张方法都用了之前讲过的卡特兰数的原理

void genPar(vector
   
     &vt,int sum, int beg, int end, int acc) {   //第0位置肯定放(，那么和这个左括号匹配的右括号可能的位置是2*i+1,然后按照此类方法再去处理括号里面的元素和括号外面的元素      vt[beg] = '(';   ++acc;   if (beg + 1 == end && acc +1 == sum){       vt[end] = ')';       for (int j=0; j< sum; ++j)           cout<
    
     =3)            genPar(vt,sum,beg+1, i - 1,acc + 1);               if (end - i >=2)            genPar(vt, sum, i+1,end,acc + i -beg );    }}void par(int left,int right, vector
     
       &vt,int count) {//left表示左括号还剩余多少个。在递归过程中只要左括号还有剩余就一定可以放左括号，但是只有当剩余的右括号的数量大于剩余的左括号的数量时，才能放右括号    if (left <0 || right 
      
       0) {        vt[count] = '(';        par(left - 1,right,vt,count + 1);    }    if (right >left){        vt[count] = ')';        par(left,right - 1,vt,count + 1);    }}int main() {       int n =3;        vector
       
         vt(2*n);    int acc = 0;   genPar(vt,2*n,0,2*n - 1,acc);   /*vector
        
          vt(6); par(3,3,vt,0);*/ }
        
       
      
     
    
   

转载地址：http://pveti.baihongyu.com/