来自：http://bbs.csdn.net/topics/350118968
搜狐：
四对括号可以有多少种匹配排列方式？比如两对括号可以有两种：（）（）和（（））
---------------------------------------------
这题直接用栈的思想就可以了，刚开始我还想直接用全排列的方法来解决，发现问题变得更加复杂了，因为重复问题不好解决，所以这里还是利用递归从简单思路出发比较方便。
1：从左边起算，左括号一定大于等于右括号
2：左括号，右括号个数均不能超过总数一半
利用上面这两个条件就可以写出递归
对于全排列问题大家可以想想。。
//============================================================================
// Name : BracketsPermutation.cpp
// Author : YLF
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
#include <iostream>
#include <list>
using namespace std;
void BracketPermutation(int left, int right, int num);
int count = 0;
list<char> arrayList;
int main() {
BracketPermutation(0,0,8);
cout<<count;
return 0;
}
void BracketPermutation(int left, int right, int num){
if(left<right)//条件一
return;
if(num == 0){
std::_List_iterator<char> it = arrayList.begin();
count++;
for(;it!=arrayList.end();it++)
cout<<*it;
cout<<endl;
}
//条件2
if(left<4){
arrayList.push_back('(');
num--;
left++;
BracketPermutation(left, right, num);
arrayList.pop_back();
num++;
left--;
}
if(right<4){
arrayList.push_back(')');
num--;
right++;
BracketPermutation(left, right, num);
arrayList.pop_back();
num--;
right--;
}
}
(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()()
()((()))
()(()())
()(())()
()()(())
()()()()
14
我检查了下4个括号和6个括号的结果：
(())
()()
2
((()))
(()())
(())()
()(())
()()()
5