一,题目
四对括号可以有多少种匹配排列方式?比如两对括号可以有两种:()()和(())
二,解答
解法一:左右括号成一对则抵消
可以将左括号看成1右括号看成 -1,然后对8个数进行全排列
对每个排列判断,是否符合条件,逐个相加,sum>=0直到遍历完该序列,符合条件则count++
如果出现sum<0则失败
解法二:采用八位bit,从0000 0000 到 1111 1111遍历,遇到0加 -1遇到1加 1
如果加完该序列所有位等于0,且递加过程中sum始终大于零则符合条件
三,源码
#include#include using namespace std ;void Print(vector v){ for (vector ::iterator beg=v.begin();beg!=v.end();++beg) cout<<*beg<<" "; cout< &v){ int nLeftBrackets=0; int nRightBrackets=0; for (vector ::iterator beg=v.begin();beg!=v.end();++beg) { if(*beg=='(') nLeftBrackets++; else nRightBrackets++; if(nRightBrackets>nLeftBrackets) return; if(nLeftBrackets+nRightBrackets==nSize&&nLeftBrackets==nRightBrackets) Print(v); } if (nLen>0) { v.push_back('('); MatchNums(nSize,nLen-1,v); v.pop_back(); v.push_back(')'); MatchNums(nSize,nLen-1,v); v.pop_back(); }}int main(){ vector v; int n=4; MatchNums(n,n,v); return 1;}