回溯在这个 "Generate Parentheses" 问题中是如何工作的？

Question

我将下面的代码放在调试器中，发现对于 n=2 的基本情况，当函数到达第 7 行时，return 语句返回并弹出最后 3 个括号。这是为什么呢，我还以为return语句应该退出函数呢？

stack = []
res = []
n=2
def backtrack(openN, closedN):
  if openN == closedN ==n:
     res.append("".join(stack))
     return

  if openN < n:
     stack.append("(")
     backtrack(openN+1, closedN)
     stack.pop()

  if closedN < openN:
     stack.append(")")
     backtrack(openN, closedN+1)
     stack.pop()

backtrack(0,0)
print(res)

结果是：['(())', '()()']

Answer 1

添加调试打印语句以跟踪整个操作是有益的。

我们调用生成括号。即调用回溯，默认参数 S = []。我们到达第二个 if，附加一个 ( 并再次调用回溯。采用相同的路径，并再次调用回溯。现在调用堆栈是：

generateParenthesis
  backtrack([], 0, 0)
    backtrac(['('], 1, 0)
      backtrack(['(','('], 2, 0)

这次left不小于n，所以取第三个if。我们附加一个右括号并再次调用回溯。这采用相同的路径，所以我们最终得到：

generateParenthesis
  backtrack([], 0, 0)
    backtrack(['('], 1, 0)
      backtrack(['(','('], 2, 0)
        backtrack(['(','(',')'], 2, 1)
          backtrack(['(','(',')',')'], 2, 2)

此时，len(S) == 2 * n为真，所以我们采用第一个选项。我们附加到 ans 列表和 return，但只有 return 来自最内层的调用。

generateParenthesis
  backtrack([], 0, 0)
    backtrack(['('], 1, 0)
      backtrack(['(','('], 2, 0)
        backtrack(['(','(',')'], 2, 1)

那个电话是在第三个 if 中间留下的。它从 S 和 returns 弹出，给我们留下

generateParenthesis
  backtrack([], 0, 0)
    backtrack(['('], 1, 0)
      backtrack(['(','('], 2, 0)

依此类推，直到最后调用returns.

回溯在这个 "Generate Parentheses" 问题中是如何工作的？

How does backtracking work in this "Generate Parentheses" question?

python

recursion

backtracking

parentheses