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

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

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

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

一、问题概述

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

二、问题分析

有效性定义：有效的括号组合必须满足两个条件：一是每个左括号(都必须有对应的右括号)与之匹配；二是任何位置上的右括号)的数量不能超过其左侧的左括号(的数量。
递归与回溯：由于需要穷举所有可能的括号排列，并检查其有效性，自然想到使用递归结合回溯的方法。递归可以帮助我们遍历所有可能的分支，而回溯则允许我们在发现当前路径不满足条件时，能够返回到上一步并尝试其他路径。
剪枝优化：在递归过程中，如果当前位置上的右括号)数量超过了左括号(的数量，或者剩余的左括号数量已经不足以匹配剩余的右括号数量，则可以提前终止当前路径的搜索，这种策略称为剪枝，能有效减少不必要的计算。

三、算法设计

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

初始化：定义一个空字符串用于存储当前的括号组合，以及两个计数器分别记录剩余的左括号和右括号的数量。
递归函数：编写一个递归函数，该函数接收当前括号组合字符串、剩余左括号数量、剩余右括号数量作为参数。
递归终止条件：当剩余左括号和右括号数量都为0时，说明已经生成了一个有效的括号组合，将其添加到结果集中。
递归逻辑：
- 如果剩余左括号数量大于0，则可以选择添加一个左括号，并递归调用函数，同时减少剩余左括号的数量。
- 如果剩余右括号数量不小于剩余左括号数量（保证有效性），则可以选择添加一个右括号，并递归调用函数，同时减少剩余右括号的数量。
回溯：在每次递归调用返回后，需要撤销上一步的操作（即删除最后添加的括号），以便尝试其他可能性。

四、代码实现

以下是使用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))。

六、总结与扩展

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

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