今天在Leetcode练习算法的时候,不禁思考一个问题,DFS和回溯算法,有什么区别呢?
先来回顾一下我们所熟知的DFS,拿FloodFill问题举例的话,先手写一个伪代码看看
1 | //int map[N][N]里面0表示海,1表示岛屿,要求一个map里面连通岛屿的个数 |
可见,传统DFS一般不会有“解空间”或者复杂解空间结构之类的说法。在之前的《算法》学习中,我一直把二者平等看待,但发现二者还是应该区别看待。DFS是一个劲的往某一个方向搜索,而回溯算法建立在DFS基础之上的,但不同的是在搜过程中,达到结束条件后,恢复状态,回溯上一层,再次搜索。状态管理是回溯的核心,回溯算法应用很多,今天就来手写三个典型的数学问题的回溯。首先,我们来看一下回溯算法的基本模板
1 | result = [] |
求N个元素的子集,从数学的角度,该子集的个数是2^n个,如果要输出这些子集呢?
1 | vector<vector<int>> res; |
输入两个数字 n, k
,算法输出 [1..n]
中 k 个数字的所有组合?
1 | vector<vector<int>>res; |
输入一个不包含重复数字的数组 nums
,返回这些数字的全部排列。
1 | List<List<Integer>> res = new LinkedList<>(); |
排列问题每次通过 contains 方法来排除在 track 中已经选择过的数字;而组合问题通过传入一个 start 参数,来排除 start 索引之前的数字。大部分回溯算法问题了,无非就是 start
或者 contains
剪枝,也没啥别的技巧了。