algorithm - 有效括号的数量

Question

我必须找出有效括号的数量。括号有两种类型 [] ,()。使用 [] ,() 的 X 和 Y 数构建有效序列有多少种方法。对于这个问题，我们认为 ([]) 是无效的方式，即 () 不能容纳 []。 有没有比递归更好的解决方案。

For Example X=1 and Y=1
[]()
()[]
[()]

Answer 1

对于任何给定的分组、自封闭圆括号的组合和给定的方括号排列，我们可以使用多集组合来确定排列的数量:

n + k - 1 choose k, where k is the smaller of the number of self-enclosed parenthetical groups and the total number of square brackets, and n is the larger of the two + 1.

方括号的排列数是第n个加泰罗尼亚数。

生成括号组的一种方法是分配越来越多的组，并计算每个分区的不同排列数(X - 分配的组数)乘以第 n 个部分的总和-加泰罗尼亚语。例如:

X = 4
Counts for each grouping:

1 group: Cat 3
2 groups: Cat 2 * 2 + 1 // partitions [2,0] * 2 and [1,1]
3 groups: 3 // partition [1,0,0] * 3
4 groups: 1 // partition [0,0,0,0]

我还没有想到避免分区的方法，并且有兴趣学习。