BackTrack or DFS?

今天在Leetcode练习算法的时候,不禁思考一个问题,DFS和回溯算法,有什么区别呢?

先来回顾一下我们所熟知的DFS,拿FloodFill问题举例的话,先手写一个伪代码看看

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//int map[N][N]里面0表示海,1表示岛屿,要求一个map里面连通岛屿的个数
//bool mark[N][N]表示该位置是否被访问过
//int go[][2]表示上下左右四个方向位置转移
int counter;
void DFS(int x,int y){
for(i in 四个方向){
int newX=x+go[i][0];int newY=y+go[i][1];
if(x越界 或者 y越界) continue;
if(该点不是1) continue;
if(该点已经被访问过) continue;
mark[newX][newY]=true; //标记访问
DFS(newX,newY);
}
}
main(){
...
for(int i=0;i<N;i++)
for(int j=0;j<N;j++){
if(该点是1 并且 该点未被访问){
counter++;DFS(i,j);
}
}
}

可见,传统DFS一般不会有“解空间”或者复杂解空间结构之类的说法。在之前的《算法》学习中,我一直把二者平等看待,但发现二者还是应该区别看待。DFS是一个劲的往某一个方向搜索,而回溯算法建立在DFS基础之上的,但不同的是在搜过程中,达到结束条件后,恢复状态,回溯上一层,再次搜索。状态管理是回溯的核心,回溯算法应用很多,今天就来手写三个典型的数学问题的回溯。首先,我们来看一下回溯算法的基本模板

1
2
3
4
5
6
7
8
9
result = []
def backtrack(路径, 选择列表或者选择的出发点):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择

求N个元素的子集,从数学的角度,该子集的个数是2^n个,如果要输出这些子集呢?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<vector<int>> res;
vector<vector<int>> subsets(vector<int>& nums){
vector<int> track;
backTrack(nums,0,track); //0表示深度,track即路径
return res;
}
void backTrack(vector<int>& nums,int start, vector<int>& track){
res.push_back(track); //这里不用判断是否满足结束条件,每一处都是结束点
for(int i=start;i<nums.size();i++)
{
//做选择
track.push_back(nums[i]);
backTrack(nums,i+1,track);
//撤销选择
track.pop_back();
}
}

输入两个数字 n, k算法输出 [1..n] 中 k 个数字的所有组合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<vector<int>>res;
vector<vector<int>> combine(int n, int k) {
if (k <= 0 || n <= 0) return res;
vector<int> track;
backtrack(n, k, 1, track);
return res;
}
void backtrack(int n, int k, int start, vector<int>& track) {
// 到达树的底部
if (k == track.size()) {
res.push_back(track);
return;
}
// 注意 i 从 start 开始递增
for (int i = start; i <= n; i++) {
// 做选择
track.push_back(i);
backtrack(n, k, i + 1, track);
// 撤销选择
track.pop_back();
}
}

输入一个不包含重复数字的数组 nums,返回这些数字的全部排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
List<List<Integer>> res = new LinkedList<>();
List<List<Integer>> permute(int[] nums) {
// 记录「路径」
LinkedList<Integer> track = new LinkedList<>();
backtrack(nums, track);
return res;
}

void backtrack(int[] nums, LinkedList<Integer> track) {
// 触发结束条件
if (track.size() == nums.length) {
res.add(new LinkedList(track));
return;
}
for (int i = 0; i < nums.length; i++) {
// 排除不合法的选择
if (track.contains(nums[i]))
continue;
// 做选择
track.add(nums[i]);
// 进入下一层决策树
backtrack(nums, track);
// 取消选择
track.removeLast();
}
}

排列问题每次通过 contains 方法来排除在 track 中已经选择过的数字;而组合问题通过传入一个 start 参数,来排除 start 索引之前的数字。大部分回溯算法问题了,无非就是 start 或者 contains 剪枝,也没啥别的技巧了。