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 回溯的过程会保证(和)成对地匹配上。关键在于两条剪枝约束：

1. 左括号优先：只要还有剩余左括号（lindex > 0），就可以放(；
2. 右括号受限：只有当前已放的左括号数量多于右括号数量（即剩余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) } }

各组成部分的作用

从源码结构看，函数通过参数传递 + 结果切片指针的方式完成回溯：每次递归生成新的字符串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, "()()") ✅ 记录 "()()" └─ (此时 lindex=2, rindex=2，不满足 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 -covermode=atomic -coverprofile=coverage.txt ./leetcode/...），可将全部题目的覆盖率结果汇总到 coverage.txt，这也是仓库「100% test coverage」主张的验证途径。

复杂度分析

• 时间复杂度：回溯只生成合法组合，其数量为第 n 个卡特兰数C(2n, n)/(n+1)；每个合法组合构造长度为2n，总复杂度为O(4^n / √n)，即O(C(2n, n)) 级别，远优于朴素枚举 + 校验的 O(n × 2^n)。
• 空间复杂度：递归深度为2n，加上结果集存储，整体为 **O(n × C(2n, n)/(n+1)) + 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