当前位置：首页>python>Python题库第5题:生成所有可能的括号()组合

Python题库第5题:生成所有可能的括号()组合

2026-06-30 12:15:51

Python，速成心法

敲代码，查资料，问Ai

练习，探索，总结，优化

★★★★★博文创作不易，源码代码的过程中，如有疑问的地方，欢迎大家指正留言交流。喜欢的老铁可以多多点赞+收藏分享+置顶，小红牛在此表示感谢。★★★★★

Python打包教程07：还不会用--add-data参数，添加资源文件吗？

Python打包教程04：UPX安装与使用（减小.exe体积）

Python打包教程03：PyInstaller命令使用指南

Python教程：PyCharm安装过程中遇到的中英文对照表

和Python编程相关的，中英文对照词汇表

2025年Python和pycharm安装下载教程

Python零基础教程：小白入门自学知识点大纲

Python教程：找到字符串中最长回文子串（上海自来水来自海上）

Python题库第2题：找出三数之和为零的数据

Python题库第3题：3[a2[c]]字符串解码

Python题库第4题：找出不含有重复字符的最长子串的长度

括号生成（中等难度）题目描述：数字 n 代表生成括号的对数，请你设计一个函数，能够生成所有可能的并且有效的括号组合。有效括号组合需满足：左括号必须以正确的顺序闭合。

# 示例输入：n = 3输出：["((()))", "(()())", "(())()", "()(())", "()()()"]输入：n = 1输出：["()"]

2.要求：不能使用 itertools 等现成组合库。时间复杂度 O(4^n / √n)（卡特兰数相关），空间复杂度 O(n)（不计输出）。

3.思路说明

a.约束条件：左括号数量不能超过 n。右括号数量不能超过左括号数量（否则会出现 )( 无效情况）。

b.回溯：递归地尝试添加左括号或右括号，直到字符串长度达到 2*n。

c.剪枝：当 right >= left 时不能再加右括号，保证了括号序列始终有效。

d.复杂度：生成卡特兰数个结果，每个结果长度为 O(n)，总时间复杂度 O(4^n / √n)。

这是括号生成的经典解法，简洁且易于理解。

↓ 完整源码如下 ↓

# -*- coding: utf-8 -*-# @Author : 小红牛# 微信公众号：wdPythondef generate_parenthesis(n: int):    """    生成所有有效的括号组合。    参数:        n: 括号对数    返回:        List[str]: 所有有效组合的列表    """    result = []    def backtrack(current: str, left: int, right: int):        """        current: 当前构建的字符串        left: 已使用的左括号数量        right: 已使用的右括号数量        """        if len(current) == 2 * n:            result.append(current)            return        # 只要还有左括号，就可以添加左括号        if left < n:            backtrack(current + '(', left + 1, right)        # 只有右括号数量小于左括号数量时，才能添加右括号        if right < left:            backtrack(current + ')', left, right + 1)    backtrack("", 0, 0)    return result# 测试用例if __name__ == "__main__":    print(generate_parenthesis(3))    # 输出: ['((()))', '(()())', '(())()', '()(())', '()()()']    print(generate_parenthesis(1))  # ['()']    print(generate_parenthesis(2))  # ['(())', '()()']