Codewars平衡括号生成问题：栈实现解法原理解析

为什么itertools.permutations会内存爆炸 #

当n=10时，要生成20个字符（10个(和10个)）的排列，permutations会生成所有可能的排列组合，其中绝大多数是非法的。即使去重后，总排列数是组合数C(20,10)=184756，但这个过程中需要先生成20!个临时排列，内存占用直接拉满，完全不高效。

栈实现解法的核心逻辑 #

先给出最常见的栈实现代码：

def generate_parenthesis(n):
    result = []
    # 栈元素格式：(当前构建的字符串, 已用左括号数, 已用右括号数)
    stack = [("(", 1, 0)]
    while stack:
        current, open_cnt, close_cnt = stack.pop()
        # 终止条件：字符串长度达到2n，说明生成了合法组合
        if len(current) == 2 * n:
            result.append(current)
            continue
        # 可以添加左括号的条件：左括号未用完
        if open_cnt < n:
            stack.append((current + "(", open_cnt + 1, close_cnt))
        # 可以添加右括号的条件：右括号数量少于左括号（保证合法）
        if close_cnt < open_cnt:
            stack.append((current + ")", open_cnt, close_cnt + 1))
    return result

逐步骤解析运行流程 #

栈在这里的作用是保存回溯的状态，每一步只生成合法的括号组合，完全避免无效路径：

1. 初始化：栈中先放入第一个合法状态——开头必须是左括号，所以初始元素是("(", 1, 0)，表示当前字符串是(，用了1个左括号、0个右括号。

2. 循环处理栈元素：每次弹出栈顶元素，分三种情况处理：

   • 终止判断：如果当前字符串长度等于2n，说明已经生成了一组合法的n对括号，直接加入结果列表。
   • 添加左括号：如果已用左括号数还没到n，就把新状态（当前字符串加(，左括号数+1，右括号数不变）压入栈。
   • 添加右括号：如果已用右括号数少于左括号数（保证不会出现())这种非法情况），就把新状态（当前字符串加)，左括号数不变，右括号数+1）压入栈。

以生成((()))为例（n=3） #

我们跟踪栈的变化，看如何得到目标组合：

• 初始栈：[("(", 1, 0)]
• 弹出("(", 1, 0)，因左括号未用完，压入("((", 2, 0)；因右括号数小于左括号，压入("()", 1, 1)，栈变为[("((", 2, 0), ("()", 1, 1)]
• 先处理("()", 1, 1)分支（栈后进先出），处理完该分支的所有子状态后，栈会回到[("((", 2, 0)]
• 弹出("((", 2, 0)，压入("(((", 3, 0)（左括号用完）和("(()", 2, 1)，栈变为[("(((", 3, 0), ("(()", 2, 1)]
• 弹出("(((", 3, 0)，无法加左括号，只能加右括号，压入("((()", 3, 1)
• 弹出("((()", 3, 1)，继续加右括号，压入("((())", 3, 2)
• 弹出("((())", 3, 2)，继续加右括号，压入("((()))", 3, 3)
• 弹出("((()))", 3, 3)，长度为6（2*3），加入结果列表，完成目标组合的生成。

栈实现的优势 #

这种方法是回溯思想的栈实现，只生成合法的括号组合，内存占用仅取决于栈的深度（最多2n层），且最终结果只存储卡特兰数级别的合法组合（n=10时卡特兰数是16796），完全不会出现内存爆炸的问题。

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