回溯算法

描述

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

只需要考虑三个问题:

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

框架

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