n对括号可以有多少种匹配排列方式(算法面试题)

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

问题:n对括号可以有多少种匹配排列方式?比如两对括号可以有两种:()()和(())

思路:问题可转化为:在一个string中包含两个字符:'('和')',他们出现的次数都为n,并且任何时候'('出现的次数总是>=')'出现的次数。

解决方案(递归):

标志:l: 左括号出现的次数,r:右括号出现的次数,n: 括号对数,s: 存储符合要求的排列字符串,num: 匹配排列种数

步骤:

1.如果r=n,即右括号已出现了n次,则num++,打印s,返回;

2.如果r=l,即左右括号出现次数相等(且<n,这由1知),则在s后面append字符‘(’,并l++,回到1(递归)

3.如果r<l,即右括号出现次数小于左括号,分两种情况

    (1),l=n,即左括号全部出现,则在s后面append字符')',并r++,回到1(递归)

    (2),l<n,则接下来出现的字符可能是'(',也可能是')'。可以:

            在s后append字符‘(’,l++,回到1(递归);然后把s最后的字符'('pop出来,append字符‘)’,l--,r++,再回到1(递归)

代码如下:

#include <string>
#include <iostream>
using namespace std;

void parenthesisArrayCount(int l,int r,int n,string s,int& num)
{
if(r==n)
{
num++;
cout<<s<<endl;
return;
}
if(r==l)
{
s.append("(");
l++;
parenthesisArrayCount(l,r,n,s,num);
}
else//r<l
{
if(l==n)
{
s.append(")");
r++;
parenthesisArrayCount(l,r,n,s,num);
}
else
{
s.append("(");
l++;
parenthesisArrayCount(l,r,n,s,num);
s.pop_back();
l--;
s.append(")");
r++;
parenthesisArrayCount(l,r,n,s,num);
}

}
return;

}
int main()
{
int num=0;
string s;
parenthesisArrayCount(0,0,4,s,num);
cout<<"共"<<num<<"种";
return 1;
}


运行结果:

n对括号可以有多少种匹配排列方式(算法面试题)

n对括号可以有多少种匹配排列方式(算法面试题)