算法习题46：四对括号可以有多少种匹配排列方式？比如两对括号可以有两种：（）（）和（（））

来自：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