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

时间:2023-01-31 04:11:16

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;
}