回溯算法 | XX雨中人

纸上得来终觉浅，绝知此事要躬行

前言

解决一个回溯问题，实际上就是一个决策树的遍历过程。你只需要思考 3 个问题：

1、路径：也就是已经做出的选择。

2、选择列表：也就是你当前可以做的选择。

3、结束条件：也就是到达决策树底层，无法再做选择的条件。

代码方面，回溯算法的框架：

result = []
function backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」

什么叫做选择和撤销选择呢，这个框架的底层原理是什么呢？下面我们就通过「全排列」这个问题来解开之前的疑惑，详细探究一下其中的奥妙！

全排列问题

知道n个不重复的数，全排列共有 n! 个。PS：为了简单清晰起见，我们这次讨论的全排列问题不包含重复的数字。

手动我们一般是这样计算：

先固定第一位为 1，然后第二位可以是 2，那么第三位只能是 3；然后可以把第二位变成 3，第三位就只能是 2 了；然后就只能变化第一位，变成 2，然后再穷举后两位……

其实这就是回溯算法，我们高中无师自通就会用，或者有的同学直接画出如下这棵回溯树，也可以成为决策树，遍历树上路径记录数字就是全排列：

为啥说这是决策树呢，因为你在每个节点上其实都在做决策：比如站在第二层第二个节点2，你现在就在做决策，可以选择 1 那条树枝，也可以选择 3 那条树枝。为啥只能在 1 和 3 之中选择呢？因为 2 这个树枝在你身后，这个选择你之前做过了，而全排列是不允许重复使用数字的。

现在可以解答开头的几个名词：[2]就是「路径」，记录你已经做过的选择；[1,3]就是「选择列表」，表示你当前可以做出的选择；「结束条件」就是遍历到树的底层，在这里就是选择列表为空的时候

完整代码实现：

/* 主函数，输入一组不重复的数字，返回它们的全排列 */
function permute(nums) {
    // 记录「路径」
    let res = [];
    backtrack(nums, res, []);
    return res;
}

// 路径：记录在 track 中
// 选择列表：nums 中不存在于 track 的那些元素
// 结束条件：nums 中的元素全都在 track 中出现
function backtrack(nums, res, track) {
    // 触发结束条件
    if (track.length == nums.length) {
        res.push(track.slice());
        return;
    }

    for (let i = 0; i < nums.length; i++) {
        // 排除不合法的选择
        if (track.includes(nums[i]))
            continue;
        // 做选择
        track.push(nums[i]);
        // 进入下一层决策树
        backtrack(nums, res, track);
        // 取消选择
        track.pop();
    }
}

但是必须说明的是，不管怎么优化，都符合回溯框架，而且时间复杂度都不可能低于 O(N!)，因为穷举整棵决策树是无法避免的。这也是回溯算法的一个特点，不像动态规划存在重叠子问题可以优化，回溯算法就是纯暴力穷举，复杂度一般都很高。

总结

回溯算法就是个多叉树的遍历问题，关键就是在前序遍历和后序遍历的位置做一些操作，算法框架如下：

backtrack(...):
    for 选择 in 选择列表:
        做选择
        backtrack(...)
        撤销选择

写backtrack函数时，需要维护走过的「路径」和当前可以做的「选择列表」，当触发「结束条件」时，将「路径」记入结果集。

其实想想看，回溯算法和动态规划是不是有点像呢？动态规划的三个需要明确的点就是「状态」「选择」和「base case」，是不是就对应着走过的「路径」，当前的「选择列表」和「结束条件」？

某种程度上说，动态规划的暴力求解阶段就是回溯算法。只是有的问题具有重叠子问题性质，可以用 dp table 或者备忘录优化，将递归树大幅剪枝，这就变成了动态规划。而上面的问题，都没有重叠子问题，也就是回溯算法问题了，复杂度非常高是不可避免的。