Backtrack问题
解决一个回溯的问题, 本质上就是在执行一个有效的遍历的问题, 遍历空间是 [选择空间] 或者叫做 [决策空间] , 或者回溯问题说是决策树的遍历问题. 所以遇到这种问题的时候, 可以在草稿纸上把决策树画出来长什么样
在具体遍历决策空间的时候, 抓住三个核心点
1.路径 onPath: 路径是当前已经做出过的选择
2.选择空间 choices: 选择空间是当前可以做的选择
3.终止条件 termination: 达到决策树的底层, 也就是无法再做选择的条件
当必须做选择, 且有多个选择的时候
vector<int> res;
void dfs(路径, 选择列表) {
if (满足终止条件) {
res.push_back(路径)
return;
}
for (选择 : 选择列表) {
// 做选择操作
dfs(路径, 选择列表)
// 做撤销选择
}
}
回溯和不回溯的区别
如果只有两种选择, 例如 494.目标和, 这里需要想一下做回溯和不做回溯的区别
vector<int> res;
void dfs(路径) {
if (满足终止条件) {
res.push_back(路径)
return
} else {
dfs(路径1)
dfs(路径2)
}
}
转载请注明来源, from goldandrabbit.github.io
