《代码随想录第二十八天》——回溯算法理论基础、组合问题、组合总和III、电话号码的字母组合
本篇文章的所有内容仅基于C++撰写。
1. 基础知识
1.1 概念
回溯是递归的副产品，它也是遍历树的一种方式，其本质是穷举。它并不高效，但是比暴力循环要快得多，在一些没有更高效解法的题目中，回溯是很好的方法。例如以下题目：
- 组合问题：N个数里面按一定规则找出k个数的集合（组合不强调元素顺序，排列强调元素顺序。）
- 切割问题：一个字符串按一定规则有几种切割方式
- 子集问题：一个N个数的集合里有多少符合条件的子集
- 排列问题：N个数按一定规则全排列，有几种排列方式
- 棋盘问题：N皇后，解数独等等
所有的回溯法都可以抽象为树形结构，因为回溯法解决的都是在集合中递归查找子集，所以集合的大小就构成了树的宽度，递归的深度就构成了树的深度。递归有终止条件，所以必然是一棵高度有限的树（N叉树）。
1.2 模板
- 回溯函数的返回值与参数
回溯算法中函数返回值一般为void，但参数需要根据具体题目确定。 - 回溯函数的终止条件
一般搜索到叶子节点就找到了答案，可以结束本次递归。 - 回溯函数的遍历过程
回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。
- 代码
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}
2. 组合
2.1 题目
组合
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1：
输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
示例 2：
输入：n = 1, k = 1
输出：[[1]]
提示：
1 <= n <= 20
1 <= k <= n
2.2 分析
这道题中的n和k值如果很大，使用for循环嵌套将会造成维数灾难。此时回溯法就发挥了很好的作用。我们使用for循环在当前集合内选一个数作为节点，再使用递归法进入下一层（以当前节点值之后的所有元素形成新的集合），然后再使用for循环选数，重复此操作，直到一条树枝上的节点数量达到目标值k。
其中，回溯操作就是在一个树枝上push_back后再进行pop_back的操作，以确保for能在同一个树层上遍历。
注意有个startindex，这个值用来确定for循环从哪个值开始遍历并进入递归
2.3 代码
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;
}
};
- 时间复杂度: O(n * 2^n)
- 空间复杂度: O(n)
3. 组合III
3.1 题目
组合III
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。
示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。
示例 3:
输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。
提示:
2 <= k <= 9
1 <= n <= 60
3.2 分析
节点累加找到相加值为n的树枝时，说明找到了一条正确的数枝。因此，这道题相对于上一题只是变更了终止条件中的结果记录方式，如果元素个数达到目标值k时，需要判断当前总值是否与目标值相等：相等则将树枝加入结果集再返回，不相等则直接return。同样会使用startindex。
另外这道题会涉及到剪枝操作：如果当前值已经大于了目标值，那么就不需要再继续遍历了。此外，for循环的范围也可以剪枝：i <= 9 - (k - path.size()) + 1，其中：
- 已经选择的元素个数：path.size();
- 所需需要的元素个数为: k - path.size();
- 列表中剩余元素（n-i） >= 所需需要的元素个数（k - path.size()）
- 在集合n中至多要从该起始位置 : i <= n - (k - path.size()) + 1，开始遍历
这个剪枝方式是横向的，因为在该类题的场景下，for循环在同层越往后遍历，集合越小，以至于节点数量可能小于了目标值k，这时候就不需要再遍历了，这些树枝就可以被剪掉。
3.3 代码
class Solution {
private:
vector<vector<int>> result; // 存放结果集
vector<int> path; // 符合条件的结果
void backtracking(int targetSum, int k, int sum, int startIndex) {
if (sum > targetSum) { // 剪枝操作
return;
}
if (path.size() == k) {
if (sum == targetSum) result.push_back(path);
return; // 如果path.size() == k 但sum != targetSum 直接返回
}
for (int i = startIndex; i <= 9 - (k - path.size()) + 1; 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;
}
};
- 时间复杂度: O(n * 2^n)
- 空间复杂度: O(n)
4. 电话号码的字母组合
4.1 题目
电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = “23”
输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]
示例 2：
输入：digits = “”
输出：[]
示例 3：
输入：digits = “2”
输出：[“a”,“b”,“c”]
提示：
0 <= digits.length <= 4
digits[i] 是范围 [‘2’, ‘9’] 的一个数字。
4.2 分析
这里的集合不再是数字，因此需要考虑映射问题，可以使用map或定义一个二维数组来完成映射。其原理与上两题类似，只是其中的startindex变为了index，其内涵也不相同。index要在给出的数字用例中遍历，例如“233”或“4567”。因此终止条件就是遍历完这些数字用例。另外注意考虑边界条件。
4.3 代码
// 版本一
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;
}
};
- 时间复杂度: O(3^m * 4^n)，其中 m 是对应三个字母的数字个数，n 是对应四个字母的数字个数
- 空间复杂度: O(3^m * 4^n)
