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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

推荐学习书目

› Learn Python the Hard Way

Python Sites

› PyPI - Python Package Index

› http://diveintopython.org/toc/index.html

› Pocoo

值得关注的项目

› PyPy

› Celery

› Jinja2

› Read the Docs

› gevent

› pyenv

› virtualenv

› Stackless Python

› Beautiful Soup

› 结巴中文分词

› Green Unicorn

› Sentry

› Shovel

› Pyflakes

› pytest

Python 编程

› pep8 Checker

Styles

› PEP 8

› Google Python Style Guide

› Code Style from The Hitchhiker's Guide

这是一个创建于 1483 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

第 1 条附言 · 2020-11-12 09:50:25 +08:00

这个看能不能看到，其实就是对这种写法很好奇，想不通

遍历

脑壳

调试

代码

22 条回复 • 2020-11-13 10:19:34 +08:00

gdw1986

2020-11-11 22:55:56 +08:00

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

JasonLaw

2020-11-11 23:23:17 +08:00 via iPhone

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

cherbim

2020-11-11 23:26:35 +08:00

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

JasonLaw

2020-11-11 23:26:54 +08:00 via iPhone

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

secondwtq

2020-11-11 23:37:10 +08:00

backtracking 了解下

freakxx

2020-11-11 23:47:41 +08:00

回溯法

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

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

freakxx

2020-11-11 23:50:35 +08:00

google

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

lithbitren

2020-11-12 00:42:41 +08:00

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

QingchuanZhang

2020-11-12 01:57:30 +08:00

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

gdw1986

2020-11-12 07:09:22 +08:00 via Android

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

gdw1986

2020-11-12 08:03:08 +08:00 via Android

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

JasonLaw

2020-11-12 08:31:25 +08:00 via iPhone

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

gdw1986

2020-11-12 08:40:39 +08:00 via Android

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

gdw1986

2020-11-12 08:41:03 +08:00 via Android

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

JasonLaw

2020-11-12 09:06:41 +08:00

@gdw1986 #11 你可以看一下

这个视频，还有这个 https://stackoverflow.com/a/24372493/5232255 。

lyyhello

2020-11-12 09:08:26 +08:00

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

gdw1986

2020-11-12 09:40:20 +08:00

@JasonLaw 十分感谢！！

mtrec

2020-11-12 09:53:38 +08:00 via Android

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

jmc891205

2020-11-12 10:17:29 +08:00

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

lithbitren

2020-11-12 14:37:59 +08:00

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

gdw1986

2020-11-12 14:41:09 +08:00 via Android

@lithbitren #20 是的，我是看了题解才过来问的

no1xsyzy

2020-11-13 10:19:34 +08:00

其实如果不是追求效率的话，这样写更清楚：

for next in "()": dfs([*A, next])

另外，不是有 step over 么，为什么要行行打断点（