22. 括号生成

解法一：数学归纳法

直接按 n=1…n 的做法，一个个写岀来，抱歉我写不出来。

解法二：递归搜索 DFS 不推荐

当 n 给定后，字符串的长度已经给定，大小为2n，每个格子都可以是 ‘(‘ 或者 ‘)’，可以生成2^2n 个候选人，然后判断候选人是否合法。

由于做了一个完全的搜索，所以时间复杂度：O(2^2n)

解法三：改进解法二，剪枝

1. 局部判断不合法，不再进行递归，例：一上来就是’)’，这肯定是不合法的
2. 2n 个格子，其中的count(左括号)==count(右括号)，并且数量一定是 n，所以递归时，每用掉一个括号，就减去一个，括号没有剩余时，则所有情况都已结束。

剪枝后，因为限制了括号数量，时间复杂度变成了 O(2ⁿ)

老师的Python 版：

Kotlin版：这里为了看得清楚 没有用字符串模板

class Solution {
    fun generateParenthesis(n: Int): List<String> {
        val res = ArrayList<String>()
        gen(0, 0, n, "", res)
        return res
    }

    /**
     * 辅助函数
     * @left 左括号剩余
     * @right 右括号剩余
     * @n 需要生成的 括号对 数
     * @result 当前结果
     */
    fun gen(left: Int, right: Int, n: Int, result: String, res: ArrayList<String>) {
        //左右括号都用完
        if (left == n && right == n) {
            res.add(result)
            return
        }
        //左括号没用完
        if (left < n) {
            gen(left + 1, right, n, result + "(", res)
        }
        //右括号不能随意拼 必须已经用了相同数量的左括号才合法
        if (left > right && right < n) {
            gen(left, right + 1, n, result + ")", res)
        }
    }
}

加餐内容：Google code style

PS：按公司规范即可