题目

输入n，表示有n/2个左括号，n/2个右括号
打印出这n个括号的有效组合

解法

深度优先搜索+

#include <iostream>

void print_result(int A[], int n , int cur){
    if(A==NULL || n<1 || cur<0 || cur>=n)
        return;
    if(A[0]==0)
        std::cout<<"{"<<std::flush;
    else
        std::cout<<"}"<<std::flush;
    for(int i=1; i<cur ; ++i){
        if(A[i]==0)
            std::cout<<" {"<<std::flush;
        else
            std::cout<<" }"<<std::flush;
    }
    for(int i=cur ; i< n ; ++i)
        std::cout<<" }"<<std::flush;
    std::cout<<std::endl;
}
long long count;
void dfs(int A[], int n, int rem, int stack_ , int cur){
    if(A==NULL || n<1 ||rem<0 || stack_<0 || cur<0 || cur>n)
        return;
    if(rem==0){
        print_result(A, n, cur);
        return;
    }
    A[cur]=0;
    dfs(A, n, rem-1, stack_+1, cur+1);
    A[cur]=1;
    dfs(A, n, rem, stack_-1, cur+1);
}

void print(int n){
    if( n<0 || n%2)
        return;
    int *A=new int[n];
    dfs(A, n, n/2, 0, 0);
    delete[] A;
}

int main()
{
    int n;
    bool blanc=false;
    while(std::cin>>n){
        if(blanc)
            std::cout<<std::endl;
        if(n==0)
            break;
        count=0;
        print(n);
        blanc=true;
    }
    return 0;
}

如果不要求打印输出，只是求出有多少个组合，那么就可以使用递推公式:
f(0)=1
f(n)=f(0)f(n-2)+f(2)f(n-1)+...+f(n-2)*f(0)

long long total_(int n){
    if(n<=0 || n%2)
        return 0;
    int *A = new int[n/2+1];
    A[0]=1;
    long long total;
    for(int i=1 ; i<n/2+1 ; ++i){
        total=0;
        for(int j=0 ; j<i/2; ++j){
            total=total+2*A[j]*A[i-1-j];
        }
        if( i%2 )
            total+=A[i/2]*A[i/2];
        A[i]=total;
    }
    delete[] A;
    return total;
}