回溯算法
描述
解决一个回溯问题, 实际上就是一个决策树的遍历流程
只需要考虑三个问题:
- 路径: 也就是已经做出的选择
- 选择列表: 当前可以做的选择
- 结束条件: 也就是到达决策树的树低, 无法再做出选择
框架
$result = [];
function backtrack(路径, 选择列表) {
if (满足结束条件) {
$result[] = 路径;
return;
}
for 选择 in 选择列表 {
做选择;
backtrack(路径, 选择列表);
撤销选择;
}
}