卡特兰数: Catalan Number

[zhouhaibing089]

近日碰到一道编程题:

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举例):

1. 先尽可能的输出左括号, 可得到:

   0 1 2 3 4 5
   | | | | | |
   ( ( ( ) ) )
   

   在此过程当中: 我们记录下那些我们可以本来可以输出右括号的地方, 有:

   index = 1, open = 2, total = 2
   index = 2, open = 3, total = 3
   

   其中:

   index: 表示该处的位置.
   open: 表示有多少个open的左括号.
   total: 表示一共输出了多少个左括号.

2. 从记录中我们取出最后一条记录, 将左括号变为右括号, 同时后续继续尽可能输出左括号. 最后一条记录为:

   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对括号的可能情形. 于是我们总结可得:

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