22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

这题很容易想到是使用递归，labuladong 模板里面提到一个递归模板，先怼过来。

result=[]

def backtrack(路径，选择列表):
  if 满足条件:
    result.add(路径)
    return

for 选择 in 选择列表:
  做选择
  backtrack(路径，选择列表)
  撤销选择

根据模板修改成如下代码

func generateParenthesis2(n int) (ans []string) {

    // 这里去掉一个路径参数
    // 这里额外加了一个参数，lCount, rCount ，否则每次要去统计 track 中的 左括号数量和右括号数量，直接取值更为方便
    var generate func(track []string, lCount, rCount int)

    generate = func(track []string, lCount, rCount int) {
        if lCount == n && rCount == n { // 满足条件加入结果
            ans = append(ans, strings.Join(track, "")) // 满足条件再将数组转成字符串，减少开销
            return
        }

        if lCount < n { // 左括号最多 n 个，不能再多了
            // 做选择
            track = append(track, "(")
            lCount++ // 左括号数量+1
            generate(track, lCount, rCount)
            // 撤销
            track = track[:len(track)-1]
            lCount-- // 左括号数量-1
        }

        if rCount < lCount { // 由括号最多和左括号数量一样，不能再多了
            // 做选择
            track = append(track, ")")
            rCount++ // 右括号数量+1
            generate(track, lCount, rCount)
            // 撤销
            track = track[:len(track)-1]
            rCount-- // 右括号数量-1
        }
    }

    generate([]string{}, 0, 0)
    return
}

题目是解答完了，但是我还是有个疑问，怎么记得之前的递归不是这样写的，但是在参数中直接传值的，也没有什么做选择和撤销选择这些啊，于是想找回以前的那种递归写法。

func generateParenthesis(n int) (ans []string) {

    var generate func(track []string, lCount, rCount int)
    generate = func(track []string, lCount, rCount int) {
        if lCount == n && rCount == n {
            ans = append(ans, strings.Join(track, ""))
            return
        }

        if lCount < n {
            generate(append(track, "("), lCount+1, rCount)
        }

        if rCount < lCount {
            generate(append(track, ")"), lCount, rCount+1)
        }
    }
    generate([]string{}, 0, 0)
    return
}

这其实是我所期待的递归写法，但是为什么这样写和那样写是等效呢，因为在进入本层递归过程中需要保持变量不变，但是进入下一层递归时候又需要变化，前面的做选择再撤销可以实现，后面的传参数也能实现，因为本轮参数根本没有变化。

代码是写给人看的，怎么好理解就该怎么使用。

参考文档

• 22. 括号生成