通俗易懂 || n 对括号可以有多少种匹配排列方式

题目

【（本科组）第十一届蓝桥杯省模拟赛】

• 由1对括号，可以组成一种合法括号序列：()。
• 由2对括号，可以组成两种合法括号序列：()()、(())。
• 由4对括号组成的合法括号序列一共有多少种？

解题思路

• 首先这是一道典型的括号匹配问题

解法一

• 关于括号匹配问题 —> 可以运用 卡特兰数（入栈顺序解法之一）
• 递推公式 h(n)=C(2n,n)/(n+1) (n=0,1,2,...)

解法二

运用 递归

• 右括号的数量不能超过左括号
• 函数的两个参数分别为 左右括号数

初始一开始 左右括号为 0

package SimulationGame12;public class bracket {
    public static int count=0,n=4;public static void main(String[] args) {
    f(0,0);System.out.println(count);}public static void f(int left,int right){
    if(left==n  ){
    count++;  // 有多种正确的匹配形式return;}f(left+1,right);if(left>right){
    f(left,right+1);}}
}

(((())))
((()()))
((())())
((()))()
(()(()))
(()()())
(()())()
(())(())
(())()() ()((()))
()(()())
()(())() ()()(())
()()()()