在这个“生成括号”的问题中，回溯是如何工作的？

pnwntuvh 于 2021-07-13 发布在 Java

关注(0)|答案(1)|浏览(301)

我将下面的代码放在调试器中，看到对于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)

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

python recursion parentheses backtracking

来源：https://stackoverflow.com/questions/67291532/how-does-backtracking-work-in-this-generate-parentheses-question

1条答案

按热度按时间

nwwlzxa71#

添加debug print语句以跟踪整个操作是有指导意义的。
我们称之为generateparenthesis。调用backtrack，默认参数为s=[]。我们到第二个了 if ，追加一个（并再次调用backtrack）。走同一条路，然后再次调用backtrack。现在调用堆栈是：

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

这次， left 不小于 n 所以我们选第三个 if . 我们附加一个右参数，然后再次调用backtrack。这条路走的是同一条路，所以我们最终得到：

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

在这一点上， len(S) == 2 * n 是真的，所以我们选择第一种选择。我们附加到 ans list和return，但只从最里面的调用返回。

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

那通电话是在第三节的中间留下的 if . 它从s弹回来，留给我们

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

以此类推，直到最后一个电话回来。

赞(0）回复(0）举报 2021-07-13

我来回答

在这个“生成括号”的问题中，回溯是如何工作的？

1条答案

相关问题

热门标签

最新问答