带有效括号的递归问题

Question

我正在尝试理解这个生成所有有效括号的解决方案。

我不明白的部分是递归如何找到所有不同的组合。当我调试代码时，我会监视整数“left”和“right”。在 generateParenthesis 中输入 2，在用 1 个有效括号填充“ans”后，在“return ans”处，我看到变量“right”减少，使 if 语句“right < left”有效。当我从未专门将其设置为这样做时，变量“正确”如何减少？简单来说，递归如何能够找到所有有效括号的情况，而不仅仅是这种情况下的一种情况？

下面我将问题与在线 Python 调试器一起包含在内，以了解我在说什么。 https://onlinegdb.com/LMNYtq3iR

https://leetcode.com/problems/generate-parentheses/

def generateParenthesis(N):
   ans = []
   S = ''
   left = 0
   right = 0
   ans = backtrack(N, S, left, right, ans)

def backtrack(N, S, left, right, ans):
   print(left)
   if len(S) == 2 * N:
      ans.append(S)
   if left < N:
      backtrack(N, S+'(', left+1, right, ans)
   if right < left:
    backtrack(N, S+')', left, right+1, ans)

   return ans
    
generateParenthesis(2)

Answer 1

变量权从不减少。您会看到早期递归执行的价值。如果在输出中包含当前递归级别，它可能会变得更清楚：

print(" "*len(S), S, left, right)

  0 0
  ( 1 0
   (( 2 0
    (() 2 1
     (()) 2 2
   () 1 1   <-- left and right do not decrease, this is the call after `( 1 0` above
    ()( 2 1
     ()() 2 2

顺便提一句，您在这里使用的 return 不一致。 backtrack 函数根本不需要 return，因为它向 ans 参数添加元素，而 generateParenthesis 根本不需要 return。我建议删除 ans 参数并将函数更改为适当的生成器函数：

def generateParenthesis(N):
   return backtrack(N, S="", left=0, right=0)

def backtrack(N, S, left, right):
   print(" "*len(S), S, left, right)
   if len(S) == 2 * N:
       yield S
   if left < N:
       yield from backtrack(N, S+'(', left+1, right)
   if right < left:
       yield from backtrack(N, S+')', left, right+1)
    
print(list(generateParenthesis(2)))

Answer 2

这与框架在 Python 中的工作方式有关。在程序的执行过程中，我们基本上从使用具有来自 generateParanthesis 的值的变量调用的回溯开始，然后由于 left 小于 N，我们得到一个对 backtrack 的递归调用，left 被迭代，程序沿着那条线继续，在递归调用之后。所以你打开了一堆新的框架，做了一堆不同的操作，在程序到达下一行之前，发现右边和左边在那个框架中是相等的，然后 return 就是答案。您正在看到类似的事情发生；本质上你进入了一个较晚的框架，然后一旦该框架关闭，return 到一个较早的框架，其中权利较少。权利从未减少，程序只是回到了权利较少的较早框架。会推荐 pythontutor.com 来可视化它。

带有效括号的递归问题

Recursion Question with Valid Parenthesis

python

algorithm

recursion

backtracking