Backtracking Algorithm

回溯算法

简介

回溯算法是搜索算法的一个子集（相辅相成），属于系统性的搜索策略。它通过深度优先遍历的方式探索所有可能的解路径，并在发现当前路径无法得到有效解时进行“回溯”（撤销选择），从而尝试其他分支。

在运用回溯算法时，我一般会画出其递归搜索树进行模拟搜索的过程，然后根据结果判断如何进行搜索以及剪枝。

模板

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

解决何类问题

回溯是搜索算法的一种实现方式，专注于穷举所有可能性，常用于解决组合、排列、子集、棋盘等问题。搜索算法更广义，包括回溯、广度优先搜索（BFS）、深度优先搜索（DFS）等。

讲解例题，只做分析，代码见leetcode 个人主页-题解>

组合问题

首先回味一下什么组合。

例如请将 nums = [1,2,3] 这个数组进行两位数的元素组合，组合的结果共有多少种？答案有三个，分别是[1,2],[1,3],[2,3]。

现在我们再来分析组合的性质：

同一元素不能重复使用，具有唯一性，不能出现结果 [1,1]
组合内的元素没有顺序区别，具有无顺序性，[1,2],[2,1]他们是一种组合
在数学上具有组合数公式，组合的数量为 $C(n,k) = C(n,n-k)$

对于组合问题在算法题目中可以细分以下几类:

数组 nums 元素不重复的组合
数组 nums 元素重复的组合
数组 nums 在满足某个 target 下的组合

对于元素不重复的组合也就是一开始所讲的 nums=[1,2,3] 中 2 个数的组合。我们首先画递归搜索树进行模拟，如下所示:

如图所示，我们的结果都是在叶子节点上。并且递归的深度也就是搜索树的高度同组合内元素个数有关，枚举的宽度同 nums 数组有关。知道这些后，我们还需要关注到具体的搜索过程上。

在搜索的过程中我们需要确保：

取 [1] 后，下一个选取的元素 nums[i] 在后续不能重复选取，即[1] -> [1,2]的过程，我们需要一个startIndex确保不重复搜索。
1. 代码随想录-组合-startIndex的由来
在得到一个结果集 [1,2] 后，需要回退到上一次取数的状态，即 [1,2] -> [1]。
在结果集满足条件（长度为 2）后，需要停止向下继续搜索，即递归的终止条件为 size == 2。

根据以上在搜索过程中需要确保的条件，再加上回溯算法的模板即可写出代码。

再到后面可以对本次搜索过程进行优化，一般我们称之为“剪枝”，也就是在搜索过程中剪去不满足条件的子树。

如前图所示，当在 [3] 节点时，发现后续没有可以取的数字时或者可取的数字不足时就可以不用再继续搜索下去。

nums = [1,2,3,4,5] 且选取 4 个数作为一组时，这个过程体现的更加明显。在[2,3,4,5]这个节点选取完之后，后续的搜索其实都不满足条件： “剩余的可选数字的数量 < 还需要选取的数字数量”。

当 nums数组的元素出现重复情况下，如何进行搜索呢？我们以 nums=[1,2,1,3]，k = 2 （k 代表从 nums 中选取的数量）为例，结果为：[1,2],[1,1],[1,3],[2,3]。

这里的 [1,1]里的数字虽然相同，但是选取的分别是nums[0] 和 nums[2] （下标不一致）属于一种组合。

这里我们先将 nums 数组进行排序（nums 数组的元素顺序和结果无关），然后再画搜索树。

【1】这个剪枝思路同上，都是后续可选数字个数不够，我们重点关注【2】的这个剪枝。

对于上述搜索过程存在重复的结果[1,2],[1,3]。应该如何避免？原始的做法就是先搜索完然后通过哈希对结果集去重，不过这在算法题中是肯定不能 AC 的。

观察 nums 数组中这 2 个 1 的选取：

对于不同树高的 1，结果是满足的
对于同树高的 1，结果是重复的。这是因为在后面对 1 的搜索结果 [1,.....]里一定是前面对 1 的搜索结果[1,......]的子集。

所以再搜索 1 时需要先判断是否同一树高里是否已经搜索过相同元素了，如果有就剪枝，反之继续搜索。

不难发现如果是不同树高的 1，那么前面的 1 一定是被选取的状态；而同树高的 1 一定是未被选取的状态。所以我们可以使用一个标记数组 status 来表示元素是否被选取。

if (i > 0 && nums[i] == nums[i - 1] && status[i - 1] = false) continue;

// 等同
if (i > startIndex && nums[i] == nums[i - 1]) continue;

对于第二个判别式，这是因为每一层的开始枚举索引为 startIndex，如果满足判别式那么就说明当前元素在前面已经搜索过了。
再回到之前的一个小细节，对 nums 数组排序，这样相同元素相邻，通过 $O(1)$ 的时间即可完成判断。

对于第三类组合问题，即组合的元素除了需要满足一定数量外还需要满足 target。

以 nums=[1,2,3], k=2, target > 3 为例（target 表示组合的大小需要 > 3）。结果集为：[1,3],[2,3]。搜索树如下：

整体和第 1、2 类组合问题没有特别的区别，注意当递归的终止，添加节点到结果集时，需要判断是否满足条件即可。

再举个例子，nums=[1,3,2,4],k = 2,target = 4 组合大小需要小于等于 4。搜索树（排序不影响组合结果）如下：

我们主要关注对[2]子树的搜索上，[2,3] > 4，那么同一层元素中后续的[2,x]也一定是大于等于 4，所以对于后续的搜索可以全部剪掉。break 掉后续的搜索，完成剪枝优化。

对于这一类 target 问题很关键的就是如何根据 target 去做剪枝优化。

相关例题：

排列问题

排列问题 (Permutation Problem) 是组合数学中的一个重要概念，也是算法和编程中经常遇到的问题类型。简单来说，排列问题就是研究从一个集合中选取若干个元素，并按照特定的顺序进行排列的方式有多少种。

举个例子，将数组[1,2,3]进行排列。

[1,2,3] （1）
[1,3,2] （2）
[2,1,3] （3）
[2,3,1] （4）
[3,1,2] （5）
[3,2,1] （6）

分析排列的性质：

同一元素不能重复使用，具有唯一性，不能出现结果 [1,1]
排列中元素是有顺序关系的，[1,2,3],[3,2,1]是不同的排列（组合和排列的一大区别）
排列问题的数学公式
1. 全排列 (n 个不同元素的全排列数)，$A(n,n) = n!$
2. 部分排列 (从 n 个不同元素中选取 k 个元素的排列数)，$A(n, k) = n!/(n-k)!$
对于[1,2,3]的全排列结果，是具有小->大的关系。
1. 字典序 (Dictionary Order) ，也称为 词典序、字典顺序或字母序，是一种用于排列字符串、单词、数字序列或其他可排序元素的序列的排序方法。它的核心思想是按照字典中单词的排列方式来比较和排序。

对于排列问题在算法题目中可以细分以下几类:

对不包含重复元素的数组/集合进行全排列
对包含重复元素的数组/集合进行全排列
特殊排列问题

以 nums=[1,2,3] 进行全排列，搜索树如下：

排列在搜索一条分支的时候会选取当前数组的全部元素，而组合则是通过 startIndex，从当前节点的下一个元素搜索。最为明显便是图中[1,3] -> [1,3,2]的搜索，这在组合中是不允许的。

再次观察，每一层的搜索元素都是不包含在父节点里的其他 nums 元素，也就是说对于节点 [2] 的下一次搜索的元素应该是 1、3。

此问题的解决和组合问题中包含重复元素的剪枝有异曲同工之妙，我们都需要一个标记数组 status[] 记录当前元素的选取状态，来确保应该搜素 nums 数组中的那些元素。

for (int i = 0; i < nums.length; i++) {
	if (status[i]) { // 当前元素已被选择
		continue;
	}
    path.add(nums[i]);
    st[i] = true;
    f(nums,st,path);
    st[i] = false;
    path.remove(path.size() - 1);
}

对于包含重复元素的全排列问题，对 nums=[1,2,1,3] （排序不影响最后的结果，除非题目要求从 nums 的状态开始搜索）的搜索如下：

这里和组合的解决思路和分析基本一致，做到分别对不同层的1做

// 如果同一树层nums[i - 1]使用过则直接跳过
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
    continue;
}
// 这种也可以，不过排列搜索思路不太清晰
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == true) {
    continue;
}

#todo 特殊排列问题

例题：

子集问题

子集问题 (Subset Problem) 是一个在计算机科学、组合数学和算法设计中经常遇到的重要问题。简单来说，子集问题通常指的是与给定集合的所有子集相关的各类问题。 它本身不是一个单一的、具体的问题，而是一类问题的统称。

给定一个集合 S，如果 T 中的所有元素也都属于 S，集合 T 是 S 的子集。任何集合都是它自身的子集，空集 ($∅$) 是任何集合的子集。

举个例子，求nums[1,2,3]的子集，结果如下：

∅
1
1,2
1,2,3
2
2,3
3

我们来分析子集具有那些性质

同一元素还是不能重复使用，不能出现子集 [1,1]
子集里的元素是没有顺序要求的，[1,2] 和 [2,1] 是同一个子集
给定一个有 n 个元素的集合，总共有 $2^n$ 个不同的子集，$2^n -1$ 个真子集
1. 当集合中的元素有重复时，计算子集的个数会有所不同

对于子集问题在算法题目中可以细分以下几类:

集合中不包含重复的元素
集合中包含重复的元素
求解特殊子集问题

还是以 nums=[1,2,3] 为例，搜索树如下：

|425

不难看出，这和组合的搜索行为几乎一样，只不过子集没有组合的个数限制，以及搜素树的节点都是所求的子集。

对于 nums=[1,1,2]，子集为[1,11,112,12,2]，搜索树如下：

这种剪枝和前面的方法是一样的，区分同层和不同层即可。

例题：