LeetCode 热题 100 | 22. 括号生成

大家好，今天我们来解决一道经典的算法题——括号生成。这道题在 LeetCode 上被标记为中等难度，要求生成所有可能的并且有效的括号组合。这是一道非常经典的回溯法题目，非常适合用来练习递归和回溯的技巧。下面我将详细讲解解题思路，并附上 Python 代码实现。

---

问题描述

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

示例 1：

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

示例 2：

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

提示：

• 1 <= n <= 8

---

解题思路

核心思想

1. 回溯法：

   • 回溯法是一种通过递归枚举所有可能解的方法。
   • 在生成括号组合的过程中，我们需要确保每个生成的括号组合都是有效的。

2. 有效括号的条件：

   • 在生成过程中，左括号的数量不能超过 n。
   • 在生成过程中，右括号的数量不能超过左括号的数量。
   • 当左括号和右括号的数量都达到 n 时，生成的括号组合是有效的。

3. 递归终止条件：

   • 当左括号和右括号的数量都达到 n 时，将当前生成的括号组合加入结果列表。

4. 递归过程：

   • 如果左括号的数量小于 n，可以添加一个左括号。
   • 如果右括号的数量小于左括号的数量，可以添加一个右括号。
   • 在递归返回时，移除最后一个括号（回溯）。

---

Python代码实现

class Solution:def generateParenthesis(self, n):""":type n: int:rtype: List[str]"""result = []def backtracking(left, right, path):# 递归终止条件if left == n and right == n:result.append(path)return# 添加左括号if left < n:backtracking(left + 1, right, path + "(")# 添加右括号if right < left:backtracking(left, right + 1, path + ")")backtracking(0, 0, "")return result

---

代码解析

1. 回溯函数 backtracking：

   • 参数：
     • left：当前左括号的数量。
     • right：当前右括号的数量。
     • path：当前生成的括号组合。
   • 递归终止条件：当左括号和右括号的数量都达到 n 时，将当前生成的括号组合加入结果列表 result。
   • 添加左括号：如果左括号的数量小于 n，可以添加一个左括号。
   • 添加右括号：如果右括号的数量小于左括号的数量，可以添加一个右括号。

2. 结果列表 result：

   • 用于存储所有生成的有效括号组合。

3. 路径字符串 path：

   • 用于存储当前递归过程中正在构建的括号组合。

---

复杂度分析

• 时间复杂度：O(2^(2n) / sqrt(n))，生成所有可能的括号组合的数量是卡特兰数。
• 空间复杂度：O(n)，递归调用栈的深度为 n，同时需要存储当前路径 path。

---

示例运行

示例 1

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

示例 2

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

---

总结

通过回溯法，我们可以高效地生成所有可能的并且有效的括号组合。这种方法利用递归枚举所有可能的括号组合，并通过回溯避免无效的组合。希望这篇题解对大家有所帮助，如果有任何问题，欢迎在评论区留言讨论！

关注我，获取更多算法题解和编程技巧！