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

时间:2021-04-29 04:10:49

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