回溯算法小总结

「回溯算法」根据当前决策有多少种选择，对应了两套模板。

模板一：输入的视角（选 or 不选）

每一次独立的决策只对应 选择 和 不选 两种情况：

  1. 确定结束回溯过程的 base case
  2. 遍历每个位置，对每个位置进行决策（做选择 -> 递归 -> 撤销选择）
1
2
3
4
5
6
7
8
9
10
11
12
void dfs(当前位置, 路径(当前结果), 结果集) { 
	if (当前位置 == 结束位置) { 
		结果集.add(路径); 
		return; 
	}
	
	选择当前位置; 
	dfs(下一位置, 路径(当前结果), 结果集); 
	撤销选择当前位置; 
	
	dfs(下一位置, 路径(当前结果), 结果集); 
}

模板二：答案的视角（枚举当前选择的结束位置）

每一次独立的决策都对应了多种选择（通常对应了每次决策能选择什么，或者每次决策能选择多少个 …）:

  1. 确定结束回溯过程的 base case
  2. 遍历所有的「选择」
  3. 对选择进行决策 (做选择 -> 递归 -> 撤销选择)
1
2
3
4
5
6
7
8
9
10
11
12
void dfs(选择列表, 路径(当前结果), 结果集) {
	if (满足结束条件) {
		结果集.add(路径); 
		return; 
	} 
	
	for (选择 in 选择列表) {
		做选择; 
		dfs(路径’, 选择列表, 结果集); 
		撤销选择; 
	}
}
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。