带有效圆括号的递归问题

Question

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

我不明白的部分是递归如何找到所有不同的组合。当我调试代码时，我会监视整数"；"左"；以及"；对"在generateParenthesign中输入2的情况下；ans"；用1个有效括号填充；return ans"；我看到变量"；右"；减少作出if语句"；右<"左"；有效的变量"；右"；当我从未专门设置它时，它会像这样减少吗？简单地说，递归如何能够找到所有有效括号的情况，而不仅仅是这种情况下的一个？

下面我把这个问题和一个在线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

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

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根本不返回。我建议去掉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中的工作方式有关。在程序的执行过程中，我们基本上从用具有generateParadistion中的值的变量调用回溯开始，然后由于left小于N，我们得到一个递归调用来回溯，left被迭代，程序沿着这条线继续，遵循递归调用。所以你打开一堆新的帧，做一堆不同的操作，在程序进入下一行之前，发现该帧中的左右相等，并返回答案。你正在看到类似的事情发生；本质上，你进入了一个较晚的帧，然后一旦该帧关闭，就返回到一个较早的帧，在该帧中，右键较少。权利从未减少，程序只是回到了权利减少的前一帧。建议使用pythontutor.com进行可视化。