《代码随想录第二十八天》——回溯算法理论基础、组合问题、组合总和III、电话号码的字母组合

《代码随想录第二十八天》——回溯算法理论基础、组合问题、组合总和III、电话号码的字母组合

本篇文章的所有内容仅基于C++撰写。

1. 基础知识

1.1 概念

回溯是递归的副产品，它也是遍历树的一种方式，其本质是穷举。它并不高效，但是比暴力循环要快得多，在一些没有更高效解法的题目中，回溯是很好的方法。例如以下题目：

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

所有的回溯法都可以抽象为树形结构，因为回溯法解决的都是在集合中递归查找子集，所以集合的大小就构成了树的宽度，递归的深度就构成了树的深度。递归有终止条件，所以必然是一棵高度有限的树（N叉树）。

1.2 模板

1. 回溯函数的返回值与参数
   回溯算法中函数返回值一般为void，但参数需要根据具体题目确定。
2. 回溯函数的终止条件
   一般搜索到叶子节点就找到了答案，可以结束本次递归。
3. 回溯函数的遍历过程
   回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。
   
4. 代码

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调整startIndexsum -= 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指向的数字转为intstring 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)