essay
hot100-括号生成
#算法
hot100——括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
提示：
1 <= n <= 8
解法
// generateParenthesis 生成所有有效的括号组合
func generateParenthesis(n int) []string {
res := make([]string, 0) // 存放结果集
backtrack(n, 0, 0, "", &res) // 从空字符串开始回溯
return res
}
// backtrack 递归回溯函数
// n: 括号对数
// left: 当前已使用的左括号数量
// right: 当前已使用的右括号数量
// cur: 当前构建的括号字符串
// res: 指向结果集的指针
func backtrack(n int, left int, right int, cur string, res *[]string) {
// 当字符串长度达到 2*n 时，说明生成了一个完整组合
if len(cur) == 2*n {
*res = append(*res, cur)
return
}
// 如果左括号数量小于 n，可以添加一个左括号
if left < n {
backtrack(n, left+1, right, cur+"(", res)
}
// 如果右括号数量小于左括号数量，可以添加一个右括号（保证有效性）
if right < left {
backtrack(n, left, right+1, cur+")", res)
}
}