算法习题46:四对括号可以有多少种匹配排列方式?比如两对括号可以有两种:()()和(())

时间:2022-06-20 15:24:44

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