v 友们！有没有简单易懂的回溯算法例子，让小弟学习一下。

V2EX = way to explore

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

现在注册

已注册用户请登录

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

回溯

小弟

易懂

算法

9 条回复 • 2020-09-18 13:13:05 +08:00

ChenFanlin

2020-09-18 11:07:00 +08:00

https://github.com/labuladong/fucking-algorithm/blob/master/%E7%AE%97%E6%B3%95%E6%80%9D%E7%BB%B4%E7%B3%BB%E5%88%97/%E5%9B%9E%E6%BA%AF%E7%AE%97%E6%B3%95%E8%AF%A6%E8%A7%A3%E4%BF%AE%E8%AE%A2%E7%89%88.md
可以看看这个

Helix225

2020-09-18 11:27:15 +08:00

探迷宫，数独生成

twllz

2020-09-18 11:37:24 +08:00

LeetCode 《 77.组合》，链接： https://leetcode-cn.com/problems/combinations/
推荐这一个题解，链接： https://leetcode-cn.com/problems/combinations/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-ma-/

总之就是这样一种模式：
```
1. 执行某种操作；
2. 在这种操作的基础上继续操作；
3. 撤回 "1" 中的操作。
```

kanglo

2020-09-18 11:43:52 +08:00

@ChenFanlin 这个 repo 真是太好了,我学算法刷题全靠这个

asanelder

2020-09-18 12:50:43 +08:00

回溯就是 DFS 吧，可以看看俺写的文章
https://segmentfault.com/a/1190000024456834

由一个很简单的直观的例子讲 DFS
然后从 DFS 的角度来看待树的三种遍历
还举了一个使用 DFS 轻松解决 leetcode 题的问题
最后引申到访问者模式，你会发现两者的相似处

以上由浅入深，举例易懂，配以图片。

请慢慢细品

asanelder

2020-09-18 12:52:10 +08:00

@ChenFanlin #1 啊看到这个博主关于树的三种遍历其本质是时间点的看法，这和俺的看法一样啊！

果然天才所见略同

CodeJr

2020-09-18 12:53:41 +08:00 via Android

全排列，八皇后老经典了

asanelder

2020-09-18 12:56:49 +08:00

俺的是用 java 举的例子
一楼那个是 python

再给楼主提个醒，回溯解题的过程就是一个树的 DFS 过程，所以，首先你要能把一个题的解想像成一颗树（几叉无所谓）

araaaa

2020-09-18 13:13:05 +08:00 via iPhone

8 皇后