卡特兰数: Catalan Number

近日碰到一道编程题:

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

一开始我的思路是(以n=3举例):

先尽可能的输出左括号, 可得到:
```
0 1 2 3 4 5
| | | | | |
( ( ( ) ) )
```
在此过程当中: 我们记录下那些我们可以本来可以输出右括号的地方, 有:
```
index = 1, open = 2, total = 2
index = 2, open = 3, total = 3
```
其中:

index: 表示该处的位置. open: 表示有多少个open的左括号. total: 表示一共输出了多少个左括号.
从记录中我们取出最后一条记录, 将左括号变为右括号, 同时后续继续尽可能输出左括号. 最后一条记录为:
```
index = 2, open = 3, total = 3
```
于是我将index=2处改为右括号, 然后重复步骤1, 可得:
```
0 1 2 3 4 5
| | | | | |
( ( ) ( ) )
```
此时, 我们的记录为:
```
index = 1, open = 2, total = 2
index = 3, open = 2, total = 3
```
于是重复步骤2, 我们可得:
```
0 1 2 3 4 5
| | | | | |
( ( ) ) ( )
```
此时, 我们的记录为:
```
index = 1, open = 2, total = 2
```
继续重复, 可得:
```
0 1 2 3 4 5
| | | | | |
( ) ( ( ) )
```
此时, 我们的记录为:
```
index = 3, open = 2, total = 3
```
继续重复:
```
0 1 2 3 4 5
| | | | | |
( ) ( ) ( )
```
于是, 可得所有记录:
```
( ( ( ) ) )
( ( ) ( ) )
( ( ) ) ( )
( ) ( ( ) )
( ) ( ) ( )
```

具体实现代码为:

// generateParenthesis generates all the well-formed parentheses combinations.
func generateParenthesis(n int) []string {
    var results []string             // results
    var b []byte = make([]byte, n*2) // string builder

    var open int  // number of open left parentheses
    var count int // number of total left parentheses
    var stack [][2]int = make([][2]int, n)
    var p int = -1

    for {
        // closed = count -open
        // position = closed * 2 + open
        position := (count-open)*2 + open
        // we can still push `(`, then do it.
        if count < n {
            // we can close if there is open parentheses, push the
            // state into stack and we'll come back.
            if open > 0 {
                p++
                stack[p] = [2]int{count, open}
            }
            b[position] = '('
            // since we added left parentheses, the number of open/total
            // parentheses are both increased by one.
            open++
            count++
            continue
        }
        // all the left parentheses are used up, we need to close them
        // all now.
        b[position] = ')'
        open--
        if open > 0 {
            continue
        }
        // now open is 0 and count is n, so we have a result.
        results = append(results, string(b))

        // if there is no history state which we can change, it means we
        // have done all the work.
        if p < 0 {
            break
        }

        // pop up a history state, and change it to right parenthese, aka
        // decrease the open number.
        count, open = stack[p][0], stack[p][1]
        position = (count-open)*2 + open
        // change to pop at location ci
        b[position] = ')'
        open--

        p--
    }

    return results
}

上面的代码中, 没有使用递归, 而是借助于一个stack来保存我们的状态信息.(也就是上面分析中所说的记录).

倘若我们要用递归实现呢, 也就是从n-1到n中间有什么联系呢?

考虑n=1: ( ).

当n=2时: 我们有: ( ) ( )以及( ( ) )

继续枚举当n=3时:

1. ( ) ( ) ( ) 
2. ( ) ( ( ) )
3. ( ( ) ) ( )
4. ( ( ) ( ) )
5. ( ( ( ) ) )

若对其归类, 可得:

1    ( ) ( )
    /
 ( )                   => ( ) { n = 2 } => ( { n = 0 } ) { n = 2 }
    \
2    ( ( ) )

3 ( ( ) ) - ( )        => ( { n = 1 } ) { n = 1 }
4   ( ) ( )
   /       \
  (         )          => ( { n = 2 } ) => ( { n = 2 } ) { n = 0 }
   \       /
5   ( ( ) )

我们定义n=0表示0对括号的可能情形. 于是我们总结可得:

$Catalan Number$

此为卡特兰数之直观解释.

zhouhaibing089 / blog

卡特兰数: Catalan Number #37