题目
输入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;
}
