algorithm - 递归方法 : How can we generate all possibilities on braces?

Question

我们如何生成大括号上的所有可能性？

N个值(value)已经给了我们，我们要产生所有的可能性。

示例:

1)如果N == 1，那么只有一种可能()。

2) 如果N==2，那么可能性是(()), ()()

3) 如果N==3，那么可能性是((())), (())(),()()(), ()(()) ...

注意:左右大括号应该匹配。我的意思是 )( 对于 N==1 是无效的

我们可以使用递归方法解决这个问题吗？

Answer 1

来自维基百科-

A Dyck word is a string consisting of n X's and n Y's such that no initial segment of the string has more Y's than X's (see also Dyck language). For example, the following are the Dyck words of length 6:

XXXYYY     XYXXYY     XYXYXY     XXYYXY     XXYXYY.

Re-interpreting the symbol X as an open parenthesis and Y as a close parenthesis, Cn counts the number of expressions containing n pairs of parentheses which are correctly matched:

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

另见 http://www.acta.sapientia.ro/acta-info/C1-1/info1-9.pdf

Abstract. A new algorithm to generate all Dyck words is presented, which is used in ranking and unranking Dyck words. We emphasize the importance of using Dyck words in encoding objects related to Catalan numbers. As a consequence of formulas used in the ranking algorithm we can obtain a recursive formula for the nth Catalan number.