输出所有的合法的括号组合

of n-pairs of parentheses.

EXAMPLE:

input: 3 (e. g. , 3 pairs of parentheses)

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

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

void genPar(vector<char> &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<<vt[j];
       cout<<endl;
       return;

   }
    for(int i = beg + 1; i<= end; i +=2 ) {
        int tmp = acc;
       
        vt[i] = ')';
        
        if (i - beg >=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<char> &vt,int count) {//left表示左括号还剩余多少个。在递归过程中只要左括号还有剩余就一定可以放左括号，但是只有当剩余的右括号的数量大于剩余的左括号的数量时，才能放右括号
    if (left <0 || right <left) return;

    if(left ==0 && right == 0) {
        for (int i = 0; i< count; ++i)
            cout<<vt[i];
        cout<<endl;
        return;
    }
    
    if(left >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<char> vt(2*n);
    int acc = 0;
   genPar(vt,2*n,0,2*n - 1,acc);

   /*vector<char> vt(6);
    par(3,3,vt,0);*/
    

}

转载自原文链接, 如需删除请联系管理员。

原文链接：输出所有的合法的括号组合，转载请注明来源！