n对括号有多少种匹配排列方式

n对括号有多少种匹配排列方式？比如一对括号有一种：（）；两对括号可以有两种：（）（）和（（））

相关知识： 卡特兰数

#include <iostream>
using namespace std;
//下述算法与没有利用到卡特兰数，只是单纯的将n对括号（共2n）个括号的所有可能排列形式的每一种进行判断，是否满足匹配；
//当前位置的括号总是先（进入bracket，然后向下递归，递归至共有2n个括号，判断当前括号和剩余括号的2n个括号是否满足括号匹配；
//然后将当前括号再重新设置为），向下递归至终止条件，判断当前括号和剩余括号的2n个括号是否满足括号匹配
//匹配数
int num=0;
int count = 0;  //每个括号有两种选择，左括号或右括号；2n个括号共有2^(2*n)种可能。
//判断当前2n个括号是否满足括号匹配；
bool isMatch(int n,char* bracket)
{
	int left_num=0,right_num=0;
	for(int i=0;i<2*n;++i)
	{
		if(bracket[i]=='l')
			left_num++;
		else if(bracket[i]=='r')
			right_num++;
		if(left_num<right_num)
			return false;
	}
	if(left_num==n && right_num==n)
	{
		for (int i = 0 ; i < 2*n; i++)
		{
			if (bracket[i]=='l')
			{
				cout<<"( ";
			}
			else
				cout<<") ";
		}
		cout<<"\n";
		return true;
	}
	else
		return false;
}
//回溯法
void BracketMatch(int n,int i,char* bracket)
{
	if(i==2*n)
	{
		if(isMatch(n,bracket))
			num++;
		count++;
		return;
	}
	else
	{
		bracket[i]='l';
		BracketMatch(n,i+1,bracket);
		bracket[i]='r';
		BracketMatch(n,i+1,bracket);
	}       
}
int main()
{
	int n;
	cin >>n;
	char* bracket=new char[2*n];
	BracketMatch(n,0,bracket);
	cout <<num<<endl;
	cout <<count<<endl;
	return 0;
}

方法二：

可以观察到，上述方法中 不管当前括号字符前面的括号是否满足匹配，总是要往下递归，至括号总数2*n 才进行最后匹配判断；其实对于当前字符，如果已经不满足匹配是不需要往下递归的，上述方法对于当前不满足匹配时不能进行递归终止。下面这种方法则可以减少无效的匹配判断。

每当进入该层时，先判断当前的括号是否满足匹配的可能，匹配（左括号的数量>=右括号的数量）则进入下一层递归，否则向下的递归直接终止。

//判断括号是否匹配
#include<iostream>
#include<cassert>
#include <vector>
using namespace std ;
void Print(vector<char> v)
{
	for (vector<char>::iterator beg=v.begin();beg!=v.end();++beg)
		cout<<*beg<<" ";
	cout<<endl;
}
void MatchNums(int nSize,int nLen,vector<char> &v,int &num)
{
	int nLeftBrackets=0;
	int nRightBrackets=0;
	for (vector<char>::iterator beg=v.begin();beg!=v.end();++beg)
	{
		if(*beg=='(')
			nLeftBrackets++;
		else
			nRightBrackets++;
		if(nRightBrackets>nLeftBrackets)
			return;
		if(nLeftBrackets+nRightBrackets==nSize&&nLeftBrackets==nRightBrackets)
		{
			num++;
			Print(v);
		}
	}
	if (nLen>0)
	{
		v.push_back('(');
		MatchNums(nSize,nLen-1,v,num);
		v.pop_back();
		v.push_back(')');
		MatchNums(nSize,nLen-1,v,num);
		v.pop_back();
	}
}
int main()
{
	vector <char> v;
	int n=8;  //n为括号总数
	int num = 0;//匹配数量
	MatchNums(n,n,v,num);
	cout<<num<<endl;
	return 0;
}