在生成括号问题中超出了Python递归深度

Question

我用蛮力求解Generate Parenthesis Problem，如下所示

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        C, ans = [], []
        ans = self.generate(C, n, ans)
        return ans

    def generate(self, C, n, ans):
        if len(C) == 2*n:
            if self.valid(C):
                ans.append(''.join(C))
        else:
            C.append('(')
            ans = self.generate(C, n, ans)
            C.pop()
            C.append(')')
            ans = self.generate(C, n, ans)
            C.pop()
        return ans


    def valid(self, C):
        bal = 0
        for c in C:
            if c == '(': bal+=1
            else: bal-=1
            if bal<0: return False
        return bal == 0

我得到以下错误

RecursionError: maximum recursion depth exceeded in comparison
Line 8 in generate(solution.py)

当我把第8行、第9行和第10行合并如下时，我不再得到错误。你知道吗

if len(C) == 2*n and self.valid(C):
    ans.append(''.join(C))

似乎有点奇怪。为什么会这样？你知道吗

任何帮助都将不胜感激。你知道吗

Answer 1

代码更改后，您的程序在逻辑上不再等同于以前的实现。 看看else分支，你就会明白，我的意思。在原始版本中，如果出现以下情况，则执行else分支：

len（C）！=2*n

在修改版本中，如果：

len（C）！=2*n与否自动生效（三）

但目前我还不明白为什么这种变化可以解释观察到的行为，因为它甚至应该产生更多的调用来生成。你知道吗

顺便说一句，如果您考虑到（）的所有组合都是有效的，那么您不需要检查逻辑，前提是在迭代过程中应用了以下条件：

• 在generate调用的每个级别上，右括号和右括号的数量最多
• 在generate调用的每个级别上，最多有n个左括号

有了这些知识，您可以使用：

class Solution2:
    def generateParenthesis(self, n: int) -> List[str]:
        C, ans = [], []
        ans = self.generate(C, n, ans, 0, 0)
        return ans

    def generate(self, C, n, ans, op, cl):
        #print(n, op, cl)
        if op < n or cl < n:
            if op < n:
                ans = self.generate(C + ['('], n, ans, op+1, cl)
            if op > cl:
                ans = self.generate(C + [')'], n, ans, op,   cl+1)
        else:
            ans.append(''.join(C))
        return ans

Answer 2

设n=2

如果我们构造一个递归树，第一个长度为2*n=2*2=4的字符串就是C="(((("

现在C的长度为2*n，但无效

所以，条件 len(C) == 2*n and self.valid(C)是False

现在else部分将被执行，程序将运行到无限递归调用中。你知道吗

PS:谢谢@Jottbe指出逻辑错误