LeetCode 22 Generate Parentheses 括号生成Go 语言 DFS 回溯解法与源码解析【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 第 22 题「Generate Parentheses括号生成」展开结合开源仓库 LeetCode-Go 中该题的完整 Go 实现与测试用例讲解如何用 DFS 回溯在不做括号匹配校验的前提下高效生成所有合法括号组合。读完本文你将掌握回溯剪枝的经典范式、该解法的时间复杂度推导以及如何在当前仓库中运行测试复现结果。题目概述题目要求给定n对括号写出一个函数生成所有可能的且有效的括号组合。例如n 3时解集为[ ((())), (()()), (())(), ()(()), ()()() ]注意解集中不包含())(、)()(这类非法组合因此问题核心是「在枚举全部 2^n 种括号排列的同时保证任意前缀中(的数量不少于)的数量」。解题思路从「事后校验」到「构造即合法」朴素思路的代价这道题乍一看会被归类为「括号匹配判断」问题先生成n个(与n个)的全排列共C(2n, n)种再逐一用栈或计数器判断合法性如 20. Valid Parentheses 的做法。但原文档明确指出如果真这么做时间复杂度会达到O(n × 2^n)——虽然对于小规模输入也能通过AC但代价极高因为大量明显非法的排列被白白生成和丢弃。核心洞察让 DFS 天然满足合法性这道题实际上不需要判断括号是否匹配。因为 DFS 回溯的过程会保证(和)成对地匹配上。关键在于两条剪枝约束左括号优先只要还有剩余左括号lindex 0就可以放(右括号受限只有当前已放的左括号数量多于右括号数量即剩余lindex rindex时才允许放)。这两条规则保证了生成的任何中间前缀中(的数量恒不小于)的数量从而最终串必然合法无需任何额外校验。源码实现详解仓库中的核心实现位于 22. Generate Parentheses.go与文档中的代码完全一致package leetcode func generateParenthesis(n int) []string { if n 0 { return []string{} } res : []string{} findGenerateParenthesis(n, n, , res) return res } func findGenerateParenthesis(lindex, rindex int, str string, res *[]string) { if lindex 0 rindex 0 { *res append(*res, str) return } if lindex 0 { findGenerateParenthesis(lindex-1, rindex, str(, res) } if rindex 0 lindex rindex { findGenerateParenthesis(lindex, rindex-1, str), res) } }各组成部分的作用组成说明generateParenthesis(n)对外入口。n 0时返回空切片边界处理否则以(n, n)作为左右括号的初始剩余数量启动递归findGenerateParenthesis(lindex, rindex, str, res)核心回溯函数。lindex表示剩余可用的(个数rindex表示剩余可用的)个数str为当前已构造的前缀串res为结果切片指针终止条件lindex 0 rindex 0时说明括号已全部用完当前str必然合法直接追加到res分支一lindex 0时放置(递归时lindex - 1rindex不变分支二rindex 0 lindex rindex时放置)递归时rindex - 1。条件lindex rindex是合法性保证的核心它意味着当前前缀中(的数量大于)的数量此时补充)不会破坏「前缀左括号不少于右括号」的不变量从源码结构看函数通过参数传递 结果切片指针的方式完成回溯每次递归生成新的字符串str(或str)不修改共享的中间状态因此无需显式的「撤销undo」步骤这也是 Go 字符串不可变特性带来的简化。递归过程演示n 2以n 2为例递归树如下generateParenthesis(2) └─ find(2, 2, ) ├─ 放 ( → find(1, 2, () │ ├─ 放 ( → find(0, 2, (() │ │ └─ 放 ) → find(0, 1, (()) │ │ └─ 放 ) → find(0, 0, (())) ✅ 记录 (()) │ └─ 放 ) → find(1, 1, ()) │ └─ 放 ( → find(0, 1, ()() │ └─ 放 ) → find(0, 0, ()()) ✅ 记录 ()() └─ (此时 lindex2, rindex2不满足 lindex rindex不能以 ) 开头)注意根节点(2, 2)处无法以)开头因为lindex rindex不成立——这正是「合法组合绝不会以右括号开头」这一事实在剪枝条件中的体现。测试用例验证仓库在 22. Generate Parentheses_test.go 中提供了标准测试qs : []question22{ { para22{3}, ans22{[]string{ ((())), (()()), (())(), ()(()), ()()(), }}, }, { para22{0}, ans22{[]string{}}, }, }测试覆盖了两个关键场景n 3的 5 种标准解集以及n 0的边界情况返回空切片而非nil。仓库采用表驱动测试风格para22与ans22分别封装输入参数与期望答案。你可以按如下方式在仓库根目录运行该题测试go test -v ./leetcode/0022.Generate-Parentheses/若希望验证整个题库的覆盖率仓库提供了 gotest.sh 脚本内部执行go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...可将全部题目的覆盖率结果汇总到 coverage.txt这也是仓库「100% test coverage」主张的验证途径。复杂度分析时间复杂度回溯只生成合法组合其数量为第 n 个卡特兰数C(2n, n)/(n1)每个合法组合构造长度为2n总复杂度为O(4^n / √n)即O(C(2n, n)) 级别远优于朴素枚举 校验的 O(n × 2^n)。空间复杂度递归深度为2n加上结果集存储整体为 **O(n × C(2n, n)/(n1)) O(2n)其中 O(2n) 为调用栈开销。变体与延伸计数而非枚举若只需统计合法组合数量可直接用卡特兰数公式或 DP对应 Unique Binary Search Trees 等思路无需真正枚举。字符串拼接优化对n较大或追求极致性能的场景可用[]byte缓冲 回溯「放置/撤销」改写避免字符串不可变带来的重复拷贝但本实现以可读性优先。回溯思想通用化本题是回溯剪枝的入门范例与仓库中 17. Letter Combinations of a Phone Number、46. Permutations、79. Word Search 等题共享同一套「选择 - 约束 - 递归 - 回溯」框架仓库 topic 目录 中的Backtracking.png也把本题列为回溯分类下的典型 Medium 题目。小结LeetCode 22 的「括号生成」是一道教科书级的回溯题。其精妙之处在于用lindex rindex一条剪枝条件替代了整份括号匹配校验逻辑使每次抵达叶子节点的字符串天然合法。仓库中的 Go 实现22. Generate Parentheses.go以极简的 17 行代码完成了这一过程配合表驱动测试与 100% 覆盖率验证是理解 DFS 回溯、卡特兰数与剪枝思想的绝佳样例。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 22 Generate Parentheses 括号生成：Go 语言 DFS 回溯解法与源码解析
LeetCode 22 Generate Parentheses 括号生成Go 语言 DFS 回溯解法与源码解析【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 第 22 题「Generate Parentheses括号生成」展开结合开源仓库 LeetCode-Go 中该题的完整 Go 实现与测试用例讲解如何用 DFS 回溯在不做括号匹配校验的前提下高效生成所有合法括号组合。读完本文你将掌握回溯剪枝的经典范式、该解法的时间复杂度推导以及如何在当前仓库中运行测试复现结果。题目概述题目要求给定n对括号写出一个函数生成所有可能的且有效的括号组合。例如n 3时解集为[ ((())), (()()), (())(), ()(()), ()()() ]注意解集中不包含())(、)()(这类非法组合因此问题核心是「在枚举全部 2^n 种括号排列的同时保证任意前缀中(的数量不少于)的数量」。解题思路从「事后校验」到「构造即合法」朴素思路的代价这道题乍一看会被归类为「括号匹配判断」问题先生成n个(与n个)的全排列共C(2n, n)种再逐一用栈或计数器判断合法性如 20. Valid Parentheses 的做法。但原文档明确指出如果真这么做时间复杂度会达到O(n × 2^n)——虽然对于小规模输入也能通过AC但代价极高因为大量明显非法的排列被白白生成和丢弃。核心洞察让 DFS 天然满足合法性这道题实际上不需要判断括号是否匹配。因为 DFS 回溯的过程会保证(和)成对地匹配上。关键在于两条剪枝约束左括号优先只要还有剩余左括号lindex 0就可以放(右括号受限只有当前已放的左括号数量多于右括号数量即剩余lindex rindex时才允许放)。这两条规则保证了生成的任何中间前缀中(的数量恒不小于)的数量从而最终串必然合法无需任何额外校验。源码实现详解仓库中的核心实现位于 22. Generate Parentheses.go与文档中的代码完全一致package leetcode func generateParenthesis(n int) []string { if n 0 { return []string{} } res : []string{} findGenerateParenthesis(n, n, , res) return res } func findGenerateParenthesis(lindex, rindex int, str string, res *[]string) { if lindex 0 rindex 0 { *res append(*res, str) return } if lindex 0 { findGenerateParenthesis(lindex-1, rindex, str(, res) } if rindex 0 lindex rindex { findGenerateParenthesis(lindex, rindex-1, str), res) } }各组成部分的作用组成说明generateParenthesis(n)对外入口。n 0时返回空切片边界处理否则以(n, n)作为左右括号的初始剩余数量启动递归findGenerateParenthesis(lindex, rindex, str, res)核心回溯函数。lindex表示剩余可用的(个数rindex表示剩余可用的)个数str为当前已构造的前缀串res为结果切片指针终止条件lindex 0 rindex 0时说明括号已全部用完当前str必然合法直接追加到res分支一lindex 0时放置(递归时lindex - 1rindex不变分支二rindex 0 lindex rindex时放置)递归时rindex - 1。条件lindex rindex是合法性保证的核心它意味着当前前缀中(的数量大于)的数量此时补充)不会破坏「前缀左括号不少于右括号」的不变量从源码结构看函数通过参数传递 结果切片指针的方式完成回溯每次递归生成新的字符串str(或str)不修改共享的中间状态因此无需显式的「撤销undo」步骤这也是 Go 字符串不可变特性带来的简化。递归过程演示n 2以n 2为例递归树如下generateParenthesis(2) └─ find(2, 2, ) ├─ 放 ( → find(1, 2, () │ ├─ 放 ( → find(0, 2, (() │ │ └─ 放 ) → find(0, 1, (()) │ │ └─ 放 ) → find(0, 0, (())) ✅ 记录 (()) │ └─ 放 ) → find(1, 1, ()) │ └─ 放 ( → find(0, 1, ()() │ └─ 放 ) → find(0, 0, ()()) ✅ 记录 ()() └─ (此时 lindex2, rindex2不满足 lindex rindex不能以 ) 开头)注意根节点(2, 2)处无法以)开头因为lindex rindex不成立——这正是「合法组合绝不会以右括号开头」这一事实在剪枝条件中的体现。测试用例验证仓库在 22. Generate Parentheses_test.go 中提供了标准测试qs : []question22{ { para22{3}, ans22{[]string{ ((())), (()()), (())(), ()(()), ()()(), }}, }, { para22{0}, ans22{[]string{}}, }, }测试覆盖了两个关键场景n 3的 5 种标准解集以及n 0的边界情况返回空切片而非nil。仓库采用表驱动测试风格para22与ans22分别封装输入参数与期望答案。你可以按如下方式在仓库根目录运行该题测试go test -v ./leetcode/0022.Generate-Parentheses/若希望验证整个题库的覆盖率仓库提供了 gotest.sh 脚本内部执行go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...可将全部题目的覆盖率结果汇总到 coverage.txt这也是仓库「100% test coverage」主张的验证途径。复杂度分析时间复杂度回溯只生成合法组合其数量为第 n 个卡特兰数C(2n, n)/(n1)每个合法组合构造长度为2n总复杂度为O(4^n / √n)即O(C(2n, n)) 级别远优于朴素枚举 校验的 O(n × 2^n)。空间复杂度递归深度为2n加上结果集存储整体为 **O(n × C(2n, n)/(n1)) O(2n)其中 O(2n) 为调用栈开销。变体与延伸计数而非枚举若只需统计合法组合数量可直接用卡特兰数公式或 DP对应 Unique Binary Search Trees 等思路无需真正枚举。字符串拼接优化对n较大或追求极致性能的场景可用[]byte缓冲 回溯「放置/撤销」改写避免字符串不可变带来的重复拷贝但本实现以可读性优先。回溯思想通用化本题是回溯剪枝的入门范例与仓库中 17. Letter Combinations of a Phone Number、46. Permutations、79. Word Search 等题共享同一套「选择 - 约束 - 递归 - 回溯」框架仓库 topic 目录 中的Backtracking.png也把本题列为回溯分类下的典型 Medium 题目。小结LeetCode 22 的「括号生成」是一道教科书级的回溯题。其精妙之处在于用lindex rindex一条剪枝条件替代了整份括号匹配校验逻辑使每次抵达叶子节点的字符串天然合法。仓库中的 Go 实现22. Generate Parentheses.go以极简的 17 行代码完成了这一过程配合表驱动测试与 100% 覆盖率验证是理解 DFS 回溯、卡特兰数与剪枝思想的绝佳样例。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考