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 或不是 self.valid(C)

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

顺便说一句。如果考虑到 ( ) 的所有组合都有效，并且在迭代过程中满足以下条件，则不需要检查逻辑:

• 在生成调用的每个级别，右括号的数量最多与左括号的数量相同
• 在生成调用的每个级别，最多有 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