刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/generate-parentheses/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

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

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

提示：

• 1 <= n <= 8

思路

我的思路第一反应就是回溯遍历。
尝试去放入左括号或者右括号，当然，会有一些限制，

• 比如左、右括号至多n个
• 右括号不能在左括号之前

而回溯的思路就是：

• 放一个之后，往下层尝试
• 然后跳回来恢复现场，换成放入另一个，再往下层尝试

好像也没什么可说的了，直接上代码。

代码

func generateParenthesis(n int) []string {
    res := make([]string, 0)
    temp := make([]byte, n*2)
    var generate func(int, int)
    generate = func(totalNum, leftNum int) {
        // 总共2n个字符就凑够了
        if totalNum == n*2 {
            res = append(res, string(temp))
            return
        }
        // 总共一共n个左括号，多了不能再放
        if leftNum < n {
            temp[totalNum] = '('
            generate(totalNum+1, leftNum+1)
        }
        // 右括号不能在左括号之前，也就是已经放入的左括号得多于右括号才能放右括号
        if totalNum-leftNum < leftNum {
            temp[totalNum] = ')'
            generate(totalNum+1, leftNum)
        }
    }
    generate(0, 0)
    return res
}