2.5 回溯算法

2.1.1 什么是回溯算法

回溯算法是一种深度优先的搜索技术，它遵循一种“试错”的思路。 在解决问题的过程中，我们通过选择某个路径并探索下去，然后发现当前选择并不是最优或者不符合约束条件时，就返回上一步重新选择路径，直到找到问题的解或者遍历完所有可能的路径。

回溯算法的步骤：

• 定义问题的解空间： 确定问题的解可表示为一个N维向量，其中N是问题的规模，一般是一个数组。

• 确定约束条件： 定义问题的解必须满足的条件，以便在搜索过程中剪枝，即找到解，进行减枝。

• 选择合适的搜索顺序： 根据问题的特点，选择合适的搜索顺序，以提高搜索效率。

• 编码回溯函数： 实现回溯函数，其中包括终止条件、约束条件的判断和路径的选择，这个是核心。

• 执行回溯搜索： 根据回溯函数进行递归搜索，记录符合条件的解并完成状态回退。 这样描述可能有点抽象，下面通过几道例题进行加深你的理解。

2.1.2 回溯算法的适用场景

回溯算法的应用领域 回溯算法可以用于解决各种问题，尤其是那些具有以下特征的问题：

• 组合问题：在给定一组候选解的情况下，找到所有可能的组合。
• 排列问题：在给定一组元素的情况下，找到所有可能的排列。
• 子集问题：在给定一组元素的情况下，找到所有可能的子集。
• 图问题：对于给定的图结构，找到满足某些约束条件的路径。

2.1.3 回溯算法模板

回溯算法可以看作森林的遍历过程。

简化成一个二维坐标：

• x为同一层级可选择的路径
• y为递归深度

模板代码：

List<?> result = new ArrayList<>();
void backtrack(路径, 选择列表):
    if (满足结束条件){
        result.add(路径)
        return
    }
    for (选择 in 选择列表){ // x
        做选择
        backtrack(路径, 选择列表) // y
        撤销选择
    }

2.4.4 回溯算法详解

2.4.5.1 leetcode 46. 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：

输入：nums = [1]
输出：[[1]]