# 回溯算法理论基础

回溯算法是一种搜索的方式，因为是递归的副产品，所以有递归就有回溯。

回溯的本质是穷举，穷举所有可能选出想要的答案，因此回溯的效率并不高。

但是一些问题只能用回溯算法来做，例如：

组合问题：N 个数里面按一定规则找出 k 个数的集合
切割问题：一个字符串按一定规则有几种切割方式
子集问题：一个 N 个数的集合里有多少符合条件的子集
排列问题：N 个数按一定规则全排列，有几种排列方式
棋盘问题：N 皇后，解数独等等

回溯解决的问题都可以抽象为树形结构，集合的大小构成了树的宽度，递归的深度构成了树的深度。

# 模板

回溯函数的返回值和参数

回溯算法的返回值一般为 void。

因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数。

回溯函数的终止条件

既然回溯可以抽象为树形结构，那么一般来说搜到叶子节点就找到了一条答案，结束本层递归。

回溯搜索的遍历过程

Alt text

for 循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个 for 循环就执行多少次。

backtracking 这里自己调用自己，实现递归。

大家可以从图中看出 for 循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了。

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

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

# 组合

题目链接🔗

可以把组合问题抽象成如下树形结构：

组合问题

可以看出这棵树，一开始集合是 1，2，3，4，从左向右取数，取过的数，不再重复取。

第一次取 1，集合变为 2，3，4 ，因为 k 为 2，我们只需要再取一个数就可以了，分别取 2，3，4，得到集合 [1,2] [1,3] [1,4]，以此类推。

每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围。

图中可以发现 n 相当于树的宽度，k 相当于树的深度。

图中每次搜索到了叶子节点，我们就找到了一个结果。

回溯函数的返回值和参数

定义两个全局变量，一个用来存放符合条件单一结果 path ，一个用来存放符合条件结果的集合 result 。

需要一个参数，为 int 型变量 startIndex，这个参数用来记录本层递归的中，集合从哪里开始遍历。

回溯函数终止条件

path 这个数组的大小如果达到 k，说明我们找到了一个子集大小为 k 的组合了。

此时用 result 二维数组，把 path 保存起来，并终止本层递归。

单层搜索的过程

for 循环每次从 startIndex 开始遍历，然后用 path 保存取到的节点 i。

	class Solution {
	private:
	vector<vector<int>> result; // 存放符合条件结果的集合
	vector<int> path; // 用来存放符合条件结果
	void backtracking(int n, int k, int startIndex) {
	if (path.size() == k) {
	result.push_back(path);
	return;
	}
	for (int i = startIndex; i <= n; i++) {
	path.push_back(i); // 处理节点
	backtracking(n, k, i + 1); // 递归
	path.pop_back(); // 回溯，撤销处理的节点
	}
	}
	public:
	vector<vector<int>> combine(int n, int k) {
	result.clear(); // 可以不写
	path.clear(); // 可以不写
	backtracking(n, k, 1);
	return result;
	}
	};

# 剪枝优化

来举一个例子，n = 4，k = 4 的话，那么第一层 for 循环的时候，从元素 2 开始的遍历都没有意义了。在第二层 for 循环，从元素 3 开始的遍历都没有意义了。

Alt text

图中每一个节点（图中为矩形），就代表本层的一个 for 循环，那么每一层的 for 循环从第二个数开始遍历的话，都没有意义，都是无效遍历。

所以，可以剪枝的地方就在递归中每一层的 for 循环所选择的起始位置。

如果 for 循环选择的起始位置之后的元素个数已经不足我们需要的元素个数了，那么就没有必要搜索了。

所以优化后的 for 循环是

for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) //i 为本次搜索的起始位置

# 组合总和 III

题目链接🔗

本题中已经决定了树的宽度是 9，深度为 k。

例如 k = 2，n = 4 的话，就是在集合 [1,2,3,4,5,6,7,8,9] 中求 k（个数） = 2, n（和） = 4 的组合。

选取过程如图：

组合总和III

确定回溯函数参数和返回值

依然定义 path 和 result 为全局变量。

接下来还需要如下参数：

targetSum 目标和，也就是题目中的 n。
k 就是题目中要求 k 个数的集合。
sum 为已经收集的元素的总和，也就是 path 里元素的总和。
startIndex 为下一层 for 循环搜索的起始位置。

确定终止条件

k 其实就已经限制树的深度，因为就取 k 个元素，树再往下深了没有意义。

所以如果 path.size () 和 k 相等了，就终止。

如果此时 path 里收集到的元素和（sum）和 targetSum（就是题目描述的 n）相同了，就用 result 收集当前的结果。

单层搜索过程

因为固定了就是 1-9 的九个数字，所以 for 循环固定 $i <= 9$ 。

搜索过程就是 path 收集每次选取的元素，sum 来统计 path 里面的和。

	class Solution {
	private:
	vector<vector<int>> result; // 存放结果集
	vector<int> path; // 符合条件的结果
	/* targetSum：目标和，也就是题目中的 n。
	** k：题目中要求 k 个数的集合。
	** sum：已经收集的元素的总和，也就是 path 里元素的总和。
	** startIndex：下一层 for 循环搜索的起始位置。
	*/
	void backtracking(int targetSum, int k, int sum, int startIndex) {
	if (path.size() == k) {
	if (sum == targetSum) result.push_back(path);
	return; // 如果 path.size () == k 但 sum != targetSum 直接返回
	}
	for (int i = startIndex; i <= 9; i++) {
	sum += i; // 处理
	path.push_back(i); // 处理
	backtracking(targetSum, k, sum, i + 1); // 注意 i+1 调整 startIndex
	sum -= i; // 回溯
	path.pop_back(); // 回溯
	}
	}

	public:
	vector<vector<int>> combinationSum3(int k, int n) {
	result.clear(); // 可以不加
	path.clear(); // 可以不加
	backtracking(n, k, 0, 1);
	return result;
	}
	};

# 剪枝

Alt text

如果已选元素总和大于 n 了，那么后面直接剪掉。

可以放在递归函数开始的地方，代码如下：

	if (sum > targetSum) { // 剪枝操作
	return;
	}

# 电话号码的字母组合

题目链接🔗

本题要解决三个问题：

数字和字母如何映射
输入 1、*、# 等异常情况。
n 个循环的问题。

数字和字母可以通过 map 或一个二维数组来做映射。

n 个循环的问题则用回溯算法解决。

输入 "23"，则抽象为以下树形结构：

Alt text

图中可以看出遍历的深度，就是输入 "23" 的长度，而叶子节点就是我们要收集的结果，输出 ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]。

确定回溯函数参数和返回值

需要两个全局变量，一个字符串 s 来收集叶子节点的结果，然后用 result 保存。

除了要遍历的字符串，还需要一个参数 index 来记录遍历第几个数字了，同时表示树的深度。

确定终止条件

终止条件是如果 index 等于输入的数字个数了，就收集结果结束本层递归。

单层搜索逻辑

首先要取 index 指向的数字，并找到对应的字符集，然后用 for 循环来处理这个字符集。

	class Solution {
	private:
	const string letterMap[10] = {
	"", // 0
	"", // 1
	"abc", // 2
	"def", // 3
	"ghi", // 4
	"jkl", // 5
	"mno", // 6
	"pqrs", // 7
	"tuv", // 8
	"wxyz", // 9
	};
	public:
	vector<string> result;
	string s;
	void backtracking(const string& digits, int index) {
	if (index == digits.size()) {
	result.push_back(s);
	return;
	}
	int digit = digits[index] - '0'; // 将 index 指向的数字转为 int
	string letters = letterMap[digit]; // 取数字对应的字符集
	for (int i = 0; i < letters.size(); i++) {
	s.push_back(letters[i]); // 处理
	backtracking(digits, index + 1); // 递归，注意 index+1，一下层要处理下一个数字了
	s.pop_back(); // 回溯
	}
	}
	vector<string> letterCombinations(string digits) {
	s.clear();
	result.clear();
	if (digits.size() == 0) {
	return result;
	}
	backtracking(digits, 0);
	return result;
	}
	};

LeetCode 递归回溯算法组合问题

# 回溯算法理论基础

# 模板

# 组合

# 剪枝优化

# 组合总和 III

# 剪枝

# 电话号码的字母组合

【代码随想录Day18】二叉树 Part.7

【代码随想录Day20】回溯算法 Part.2