### 问题描述
卡特兰遇到了一个非常棘手的问题,他现在有许多对括号,他想知道这些括号有多少种有效的组合方式。
一个有效的括号配对定义为:
(
后面都必须在某个位置有一个对应的闭括号 )
。利用这些定义,我们可以确保:
)(
这样的无效组合。给定一个整数 n,代表 n 对括号。你的任务是确定这 n 对括号能够生成多少种有效的配对方法。一个有效的括号配对是指每一个开括号都与一个闭括号正确配对,并且没有多余的开或闭括号。
例如,对于 n=3,存在的有效配对有 ((()))
,(()())
,(())()
,()(())
与 ()()()
。
一个整数 n,(1≤n≤30),代表括号的对数。
一个整数,表示 n 对括号能形成的有效配对方法数。
3
5
如上述问题描述中提到的,对于 n=3,存在的有效配对有 5 种:((()))
,(()())
,(())()
,()(())
与 ()()()
。
输入中的整数 n 满足 1≤n≤30。