如何用Python生成指定长度N的所有有效括号排列？

问题描述 #

给定整数N，生成所有由N对括号组成的有效排列。有效括号需满足两个条件：

• 任意前缀中左括号的数量不小于右括号的数量
• 最终左、右括号的总数均为N

示例：

• 当N=1时，输出：['()']
• 当N=3时，输出：['()(())', '(())()', '(()())', '((()))', '()()()']

解决思路 #

采用回溯法递归生成所有可能的组合，同时通过两个规则剪枝，避免生成无效组合：

1. 左括号使用数量未达到N时，可追加左括号
2. 右括号使用数量小于左括号时，可追加右括号

这种方式能保证每一步生成的字符串都是有效前缀，最终自然得到所有符合要求的完整排列。

代码实现（Python） #

def generate_parentheses(n):
    result = []
    def backtrack(current_str, open_count, close_count):
        # 终止条件：左右括号均已用完
        if open_count == n and close_count == n:
            result.append(current_str)
            return
        # 左括号未达上限，添加左括号继续递归
        if open_count < n:
            backtrack(current_str + '(', open_count + 1, close_count)
        # 右括号数量少于左括号，添加右括号继续递归
        if close_count < open_count:
            backtrack(current_str + ')', open_count, close_count + 1)
    backtrack('', 0, 0)
    return result

# 测试示例
print(generate_parentheses(1))  # 输出: ['()']
print(generate_parentheses(3))  # 输出: ['((()))', '(()())', '(())()', '()(())', '()()()']

代码解释 #

• backtrack是核心递归函数，参数分别为当前构建的字符串、已使用左括号数、已使用右括号数
• 当左右括号使用数均等于N时，将当前字符串存入结果列表
• 优先尝试添加左括号（只要未达N），再尝试添加右括号（必须保证右括号数少于左括号，避免出现())这类无效前缀）
• 递归过程会遍历所有有效路径，最终收集到全部合法的括号排列

内容的提问来源于stack exchange，提问作者Fijaja Mulla