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