如何仅用递归将单类型有效括号生成扩展至三种括号？

你遇到的核心问题在于，单括号场景只需要跟踪开闭数量就能保证有效性，但多括号场景必须跟踪未闭合括号的嵌套顺序——只有最后打开的括号才能最先闭合（栈的后进先出规则）。

不需要借助额外数据结构，我们可以通过递归参数传递一个字符串来模拟这个"栈"，记录当前未闭合的左括号类型序列。以下是具体实现方案：

核心思路 #

• 用两组参数分别跟踪三种括号的已使用数量：左括号(, [, {的已用计数，以及对应的右括号已用计数
• 用字符串open_stack模拟栈，记录当前未闭合的左括号顺序（比如"([{"表示先打开了(，接着[，再接着{）
• 递归分支分为两种：
  1. 尝试添加左括号：如果该类型左括号未达n个，就追加到当前序列，更新对应计数，并将该类型加入open_stack末尾
  2. 尝试添加右括号：如果该类型右括号未达n个，且open_stack的最后一个字符是对应的左括号，就追加右括号，更新对应计数，并移除open_stack的最后一个字符（模拟栈弹出）

代码实现 #

def generate_three(n, left_counts=(0,0,0), right_counts=(0,0,0), seq="", open_stack=""):
    # 终止条件：所有括号都用完（每种左、右括号各n个）
    if all(c == n for c in left_counts) and all(c == n for c in right_counts):
        print(seq)
        return
    
    # 定义括号类型映射：左括号 -> 对应的右括号，以及索引
    bracket_pairs = [("(", ")", 0), ("[", "]", 1), ("{", "}", 2)]
    
    # 尝试添加左括号的分支
    for left, right, idx in bracket_pairs:
        if left_counts[idx] < n:
            # 更新左括号计数，追加左括号到序列，左括号类型加入open_stack
            new_left_counts = list(left_counts)
            new_left_counts[idx] += 1
            generate_three(n, tuple(new_left_counts), right_counts, seq + left, open_stack + left)
    
    # 尝试添加右括号的分支
    for left, right, idx in bracket_pairs:
        if right_counts[idx] < n and open_stack.endswith(left):
            # 更新右括号计数，追加右括号到序列，移除open_stack的最后一个字符
            new_right_counts = list(right_counts)
            new_right_counts[idx] += 1
            generate_three(n, left_counts, tuple(new_right_counts), seq + right, open_stack[:-1])

# 调用示例：生成每种括号2个的所有有效组合
generate_three(2)

方案说明 #

• 这里没有使用任何显式数据结构（如列表、栈对象），所有状态都通过递归参数传递：left_counts和right_counts用元组记录数量，open_stack用字符串模拟栈（每次递归传递新的字符串，避免状态污染）
• 递归过程严格遵循有效括号的规则：只有存在未闭合的对应左括号时，才能添加右括号；左括号未达上限时可以随时添加
• 最终生成的序列满足每种括号恰好n个，总长度为6n，且所有组合都是有效的平衡括号表达式

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