一天一道力扣Hot100（37）：深度优先算法--括号生成

LeetCode 22. 括号生成（Go 语言实现）

个人主页：
> 我不会起名字322 < （欢迎各位大佬莅临😊）

其他栏目：
> 技术栈学习笔记 <

其他栏目：
> 力扣Hot100题目解析 <

其他栏目：
> Go项目学习笔记 <

前言：

上一篇组合总和里，我总结出了回溯的"三要素"：路径、选择列表、结束条件。当时我说"一旦想清楚这三样东西，剩下的就是套模板"。

今天这道括号生成，正好是检验这句话的好例子——它和组合总和长得很不一样，没有数组、没有 startIndex、没有求和，但本质上还是同一套东西。我们一起来看看，三要素在这道题里分别变成了什么。

整体的一个模板还是这样的：

func backtrack(路径, 选择列表) {
if 满足结束条件 {
结果集 = append(结果集, 路径的拷贝)
return
}
for 选择 := 选择列表 {
做选择 // 路径加入该选择
backtrack(路径, 新的选择列表)
撤销选择 // 路径移除该选择
}
}

下面我们来看一道题目深入理解一下

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

示例 1：

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

示例 2：

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

示例 3：

输入：n = 0
输出：[""]

有效括号的条件

在动手写代码之前，先想清楚"什么样的括号组合才算有效"。有两个条件缺一不可：

第 2 条尤其关键。比如 "())(" 虽然左括号右括号都是 2 个，但中途右括号一度超过了左括号，所以不合法。这个条件直接决定了我们的剪枝策略。

• 首先，我们不需要排序，也不需要数组。这道题的输入只有一个整数 n，没有候选数组，所以组合总和里的 sort.Ints 和 startIndex 在这里都用不上。这正说明：三要素是本质，具体形式随题目而变。

• 其次，我们要定义几个数据

• 一个是当前已经拼出来的括号字符串（路径）

  path := make([]byte, 0, 2*n) // 用 []byte 避免频繁字符串拼接

• 一个是结果集，用来写入结果

  result := []string{}

• 上面两个是确定的，最后一个看题目不同来自己确定。这道题我们需要记录已经用了几个左括号、几个右括号，用来判断下一步能放什么、以及什么时候结束

  open, close := 0, 0

  注意：这里不像组合总和那样传 curSum，因为括号题没有"和"要凑，取而代之的是两个计数器。

• 有了上面的数据，我们现在来套用模板来写这道题目

  func backtrack(路径, 选择列表) {
  首先是这个大框架，路径肯定要传参 path，选择列表呢？
  这道题的选择列表不是数组，而是由 open 和 close 两个变量动态决定的：
  – open < n 时，可以放 '('
  – close < open 时，可以放 ')'
  }

  if 满足结束条件 {
  这里的满足条件就是 len(path) == 2*n

  这里的路径拷贝就是把当前符合答案标准的 path 转成 string 写入结果集
  结果集 = append(结果集, string(path))
  return
  }
  //这里我们要想，如果还能放括号怎么办呢？显然，继续下面的递归即可
  //那如果既不能放左括号、也不能放右括号呢？这种情况其实不会出现，
  //因为只要没到 2*n，open < n 或 close < open 至少有一个成立

  // 选择一：放左括号
  if open < n {
  path = append(path, '(')
  backtrack(open+1, close)
  path = path[:len(path)–1] // 撤销选择
  }

  // 选择二：放右括号（右括号不能多于左括号，这就是剪枝）
  if close < open {
  path = append(path, ')')
  backtrack(open, close+1)
  path = path[:len(path)–1] // 撤销选择
  }

• 因此，我们最后改造的函数就是

  func generateParenthesis(n int) []string {
  result := []string{}
  path := make([]byte, 0, 2*n) // 预分配容量

  var backtrack func(open, close int)
  backtrack = func(open, close int) {
  // 结束条件：括号用完
  if len(path) == 2*n {
  result = append(result, string(path))
  return
  }

  // 选择一：加左括号
  if open < n {
  path = append(path, '(')
  backtrack(open+1, close)
  path = path[:len(path)–1] // 回溯
  }

  // 选择二：加右括号（右括号不能多于左括号，这就是剪枝）
  if close < open {
  path = append(path, ')')
  backtrack(open, close+1)
  path = path[:len(path)–1] // 回溯
  }
  }

  backtrack(0, 0)
  return result
  }

复杂度分析

• 时间复杂度：O(4ⁿ / √n)，即第 n 个卡特兰数
• 空间复杂度：O(n)，递归栈深度（不算结果存储）

总结

回过头看，这道题再次印证了"回溯三要素"：

和组合总和对比一下，区别一目了然：

题目变了，形式变了，但三要素的骨架没变。这就是为什么我说"想清楚这三样，剩下的就是套模板"。

本文是 《算法题目解析系列》 的第 [37] 篇，本系列将持续更新，每篇都提供清晰的思路与编程语言实现。欢迎关注，第一时间获取更新。如果你有想看的题目，也可以在评论区留言告诉我。