30 | 面试题：生成有效括号组合-算法面试通关 50 讲

当前位置:　首页>> 技术小册>> 算法面试通关 50 讲

### 30 | 面试题：生成有效括号组合

在算法面试中，生成有效括号组合是一道经典且富有挑战性的题目。它不仅考察了面试者对递归、回溯算法的理解，还间接评估了其对栈这种数据结构的掌握程度。本章节将深入剖析这个问题，从问题分析、算法设计到代码实现，全方位解析如何高效地生成所有有效的括号组合。

#### 一、问题概述

题目要求：给定一个整数`n`，代表需要使用的括号对数（即左括号`(`和右括号`)`各`n`个），要求编写一个函数来生成所有可能的、并且有效的括号组合。例如，当`n = 3`时，有效的括号组合包括`"((()))"`, `"(()())"`, `"(())()"`, `"()(())"`, `"()()()"`。

#### 二、问题分析

1. **有效性定义**：有效的括号组合必须满足两个条件：一是每个左括号`(`都必须有对应的右括号`)`与之匹配；二是任何位置上的右括号`)`的数量不能超过其左侧的左括号`(`的数量。

2. **递归与回溯**：由于需要穷举所有可能的括号排列，并检查其有效性，自然想到使用递归结合回溯的方法。递归可以帮助我们遍历所有可能的分支，而回溯则允许我们在发现当前路径不满足条件时，能够返回到上一步并尝试其他路径。

3. **剪枝优化**：在递归过程中，如果当前位置上的右括号`)`数量超过了左括号`(`的数量，或者剩余的左括号数量已经不足以匹配剩余的右括号数量，则可以提前终止当前路径的搜索，这种策略称为剪枝，能有效减少不必要的计算。

#### 三、算法设计

基于上述分析，我们可以设计如下算法：

1. **初始化**：定义一个空字符串用于存储当前的括号组合，以及两个计数器分别记录剩余的左括号和右括号的数量。

2. **递归函数**：编写一个递归函数，该函数接收当前括号组合字符串、剩余左括号数量、剩余右括号数量作为参数。

3. **递归终止条件**：当剩余左括号和右括号数量都为0时，说明已经生成了一个有效的括号组合，将其添加到结果集中。

4. **递归逻辑**：
   - 如果剩余左括号数量大于0，则可以选择添加一个左括号，并递归调用函数，同时减少剩余左括号的数量。
   - 如果剩余右括号数量不小于剩余左括号数量（保证有效性），则可以选择添加一个右括号，并递归调用函数，同时减少剩余右括号的数量。

5. **回溯**：在每次递归调用返回后，需要撤销上一步的操作（即删除最后添加的括号），以便尝试其他可能性。

#### 四、代码实现

以下是使用Python实现的代码示例：

```python
def generateParenthesis(n):
    def backtrack(s, left, right):
        if len(s) == 2 * n:  # 递归终止条件
            result.append(s)
            return
        if left < n:  # 剩余左括号数量大于0
            backtrack(s + '(', left + 1, right)
        if right < left:  # 剩余右括号数量不小于剩余左括号数量
            backtrack(s + ')', left, right + 1)

result = []
    backtrack("", 0, 0)
    return result

# 示例
n = 3
print(generateParenthesis(n))
```

#### 五、算法复杂度分析

- **时间复杂度**：由于需要生成所有可能的括号组合，并检查其有效性，时间复杂度为指数级。具体来说，对于`n`对括号，有效组合的数量由卡特兰数给出，约为`4^n / (n * sqrt(πn))`，因此时间复杂度可以近似为O(4^n / sqrt(n))。

- **空间复杂度**：递归过程中，系统栈的深度最大可达`2n`（当所有括号都按顺序排列时），同时还需要存储结果集，因此空间复杂度为O(n)加上结果集的大小，后者在最坏情况下接近O(4^n / sqrt(n))。

#### 六、总结与扩展

通过本题，我们不仅掌握了如何使用递归和回溯算法解决组合问题，还深刻理解了有效括号组合的特性及其生成逻辑。此外，本题还可以进一步扩展，比如增加括号种类的数量（如加入花括号`{}`和方括号`[]`），或者对生成的括号组合进行排序等。这些扩展都能加深我们对算法的理解和应用能力。

总之，生成有效括号组合是一道极具代表性的算法面试题，它不仅考察了面试者的编程技能，还考验了其逻辑思维和问题解决能力。希望本章内容能帮助读者更好地掌握这一知识点，并在未来的面试中脱颖而出。

该分类下的相关小册推荐：

编程之道-算法面试(上)

业务开发实用算法精讲

数据结构与算法之美

数据结构与算法(上)

数据结构与算法(下)

编程之道-算法面试(下)

数据结构与算法(中)