回溯算法（第一章 基础）
这一章我们只讲思想，不做复杂题。
- 前提条件
回溯（Backtracking）不是一种数据结构。
也不是一种具体算法。
它是一种：算法设计思想
主要解决：
枚举所有方案
搜索所有可能
找满足条件的方案
剪枝优化
典型题：
子集
组合
排列
N皇后
数独
组合总和
- 回溯到底是什么？
试一条路
↓
如果不行
↓
退回来
↓
换另一条路
所以：Backtracking
↓
回退
↓
回溯
例如：
走迷宫：
A
/ \
B C
/
D
走：
A
↓
B
↓
D
发现：
死路
于是：
退回B
↓
退回A
↓
走C
这就是：
回溯。
- 回溯和DFS区别
DFS
是一种遍历方式。
例如：
树：
0
↓
1
↓
2
DFS：访问所有节点。
而回溯：
不是为了遍历。
而是枚举所有可能。
例如：
123
所有排列
DFS：
只是访问：
1
2
3
回溯：
123
132
213
231
312
321
完全不是一个目标。
- 回溯为什么是DFS升级？
因为它也是：
一路走到底。
例如：
组合：
1
↓
2
↓
3
但是：
DFS到底结束。
直接：return
然而回溯：
到底以后
还要撤销刚刚的选择。
例如：
path
↓
[1]
↓
[1,2]
↓
[1,2,3]
结束。
不是直接结束。
而是：
删除3
↓
删除2
↓
继续尝试其它数字
所以：
回溯：
比DFS：
多了一步恢复现场。
- 回溯的四步
① 做选择
↓
② 递归
↓
③ 撤销选择
↓
④ 换另一种选择
也即是：
选择
↓
递归
↓
恢复
↓
继续
- 回溯为什么必须恢复？
举个例子。
例如：
求：
123
所有排列
开始：
path
[]
选择：
1
path：
[1]
继续：
选择：
2
path：
[1,2]
继续：
3
得到：
[1,2,3]
记录答案。结束。
现在如果不恢复path：
还是[1,2,3]
那么以后根本没法尝试：
1
3
2
所以必须删掉3
变[1,2]
继续。
- 回溯固定模板
void dfs(...)
{
if(结束条件)
{
保存答案;
return;
}
for(...)
{
做选择;
dfs(...);
撤销选择;
}
}
- 一个例子
例如：
从：
1
2
3
任选。
代码：
void dfs()
{
for(int i=1;i<=3;i++)
{
printf("%d ",i);
}
}
这不是回溯。
因为没有恢复。
真正回溯：
path.push(i);
dfs();
path.pop();
这里：
push
↓
递归
↓
pop
就是回溯。
-
回溯代码模板
void dfs(...)
{
if(满足条件)
{
保存答案;
return;
}for(...)
{
//① 做选择
path[pathSize++] = 当前元素;//② 递归 dfs(...); //③ 撤销选择 pathSize--;}
}
pathSize--
不是删除数组。
而是逻辑删除。
以后都会这样写
- 回溯为什么不用真的删除？
例如数组：
path
↓
1
2
3
现在：
pathSize=3;
删除：
3
其实代码只有：
pathSize--;
变成：
pathSize=2
数组实际上还是：
1
2
3
只是以后只看前2个。
所以效率：非常高。
- 回溯总结
Backtracking
核心思想：
做选择
↓
递归搜索
↓
撤销选择
↓
尝试下一种可能
与DFS区别：
DFS：
遍历
Backtracking：
搜索所有方案
固定模板：
for
↓
选择
↓
递归
↓
恢复
↓
继续