algorithm - 平衡括号

Question

我想知道是否有人可以回答我，这是在下一个问题的回溯解决方案中生成的结果数量：

给定 n 对括号，编写一个函数来生成格式正确的括号的所有组合。

例如，给定 n = 3，解集是：

“((()))”、“(()())”、“(())()”、“()(())”、“()()()”

stackoverflow中有一篇相关的帖子：Generate balance parentheses in java

我怀疑是否有一个公式可以给我计算之前可以生成的有效括号的数量。例如：
- f(n):
- f(1) = 1
- f(2) = 2
- f(3) = 5
等等..

谢谢你。

Answer 1

包含正确匹配的 n 对括号的数字表达式可以通过加泰罗尼亚数字计算。引用维基百科的相关链接：

组合数学中有许多计数问题，其解决方案由加泰罗尼亚数给出……Cn 是长度为 2n 的 Dyck 单词的数量。一个 Dyck 词是一个由 n 个 X 和 n 个 Y 组成的字符串，使得字符串的任何初始段中的 Y 都比 X 多……重新解释符号 X 为左括号，Y 为右括号，Cn 计算表达式的数量包含 n 对正确匹配的括号。

第 n 个加泰罗尼亚数直接根据二项式系数给出：