Skip to main content

回溯算法

描述

解决一个回溯问题, 实际上就是一个决策树的遍历流程

只需要考虑三个问题:

  • 路径: 也就是已经做出的选择
  • 选择列表: 当前可以做的选择
  • 结束条件: 也就是到达决策树的树低, 无法再做出选择

框架

$result = [];
function backtrack(路径, 选择列表) {
if (满足结束条件) {
$result[] = 路径;
return;
}
for 选择 in 选择列表 {
做选择;
backtrack(路径, 选择列表);
撤销选择;
}
}