谁能给仔细讲讲这个递归该咋理解吗？

[gdw1986]

我是打开调试都想不通到底是怎么实现遍历所有组合的，脑壳疼。

[gdw1986]

https://imgur.com/cao8ZKd
补个图片链接，实在不会插图

[JasonLaw]

你说的应该是 https://leetcode.com/problems/generate-parentheses/description/ 吧？

[cherbim]

建议你把问题补充完全，你这代码没有上下文，

[JasonLaw]

如果我没理解错的话，就是通过递归产生所有可能，然后最后检查是否有效，其实就是 brute force 。但是我不太理解 A.pop()的作用是什么。

[secondwtq]

backtracking 了解下

[freakxx]

回溯法

你可以理解，不过你代码少了一行空格行，不然代码就很好理解

for sign in ["(", ")"]
就是做了这么个操作
先拼接上去，然后检验，不行就去掉，换另一个上去试

[freakxx]

google

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。 但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。 许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。

[lithbitren]

为啥 v2 总是喜欢用境外图床贴图啊，经常看不到图，不过如果说的是回溯算法的其实可以按照递归函数参数走一遍画一颗树出来就知道是怎么遍历的了。顺便，leetcode22 和面试金典 08.09 的最短的 python 题解是我写的，不过那种写法仅适合 py/js 这种全堆解释型语言，其他静态语言还是老老实实 push/pop 比较快。

[QingchuanZhang]

学一下 dfs 就好了，入栈 push，出栈 pop

[gdw1986]

@JasonLaw #2 是的，哈哈，被发现了

[gdw1986]

@lithbitren #8 是的我现在的问题在于不知道是怎么回溯的，我再开调试试试，主要觉得这个写法跟我的想法很契合，但是我没写出来

[JasonLaw]

@gdw1986 #11 你这个不是 backtracking 吧，比如 n 是 1，你这个算法不是会产生[((, (), )(, ))]四种可能吗？

[gdw1986]

@JasonLaw #12 不会，有条件的，判断了长度才 append

[gdw1986]

@JasonLaw #12 而且输入的是 n，不好意思我没贴全

[JasonLaw]

@gdw1986 #11 你可以看一下 <amp-youtube data-videoid="sz1qaKt0KGQ" layout="responsive" width="480" height="270"></amp-youtube> 这个视频，还有这个 https://stackoverflow.com/a/24372493/5232255 。

[lyyhello]

你写两个一模一样的方法体。只是方法名不一样。相互调。你就懂了

[gdw1986]

@JasonLaw 十分感谢！！

[mtrec]

本质就是树的遍历 如果你知道先序遍历后序遍历访问节点的时机 那回溯就很好理解了 进入之前做准备动作 判断完成条件 遍历左右子树 离开节点重置

[jmc891205]

你把子问题的边界条件和递归式想明白 就很容易理解整个递归了

[lithbitren]

python 全局变量可以直接访问，其实 A 不用放进函数里传参，遍历递归函数可以把 A 的状态作为参考画数，append 的时候就加元素，这里有两个分支，一个左括号一个右括号，右括号数不大于左括号数，左右括号同时等于 n 时输出，pop 的时候就直接减元素，n=3 情况下树很好画的。
不过这代码的条件判断还是不太友好，leetcode 有原题，python 还可以写得更简洁。
https://leetcode-cn.com/problems/bracket-lcci/comments/