文心 LeetCode 22. 括号生成 Golang实现

LeetCode 22. 括号生成 — Golang 实现问题描述给定n对括号生成所有由n对括号组成的有效格式正确的括号组合。输入: n 3输出: [“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]解题思路回溯法核心规则• 任意时刻左括号数left≥ 右括号数right保证合法性• 左括号总数 ≤n• 右括号总数 ≤n“” / \ “(” 无效(leftright) / \ “((” “()” / \ / “(((” “(()” “()(” “())” ← “())” 非法leftright…代码实现方法一回溯推荐【go】package mainimport “fmt”func generateParenthesis(n int) []string {var result []stringbacktrack(result, “”, 0, 0, n)return result}// backtrack 回溯函数// left: 已使用的左括号数// right: 已使用的右括号数func backtrack(result[]string, current string, left, right, n int) {// 终止条件当前字符串长度达到 2nif len(current) 2*n {*result append(*result, current)return}// 尝试添加左括号if left n {backtrack(result, current“(”, left1, right, n)}// 尝试添加右括号必须 left right 才合法if right left {backtrack(result, current“)”, left, right1, n)}}func main() {fmt.Println(generateParenthesis(3))// 输出: [((())) (()()) (())() ()(()) ()()()]}方法二迭代方式BFS 队列【go】func generateParenthesis2(n int) []string {if n 0 {return []string{“”}}var result []string// 队列元素: [当前字符串, 左括号数, 右括号数]queue : [][3]interface{}{{“”, 0, 0}}for len(queue) 0 {cur : queue[0]queue queue[1:]s : cur[0].(string)left : cur[1].(int)right : cur[2].(int)if left n right n {result append(result, s)continue}if left n {queue append(queue, [3]interface{}{s “(”, left 1, right})}if right left {queue append(queue, [3]interface{}{s “)”, left, right 1})}}return result}复杂度分析【表格】指标 值时间复杂度 O(4ⁿ/√n)即第 n 个卡特兰数空间复杂度 O(4ⁿ/√n)结果存储 O(n)递归栈深关键点总结剪枝条件right left → 才能放右括号2. 终止条件left n right n → 字符串长度为 2*n3. 字符串拼接Go 中使用 拼接每次产生新字符串