第22天，回溯章节开始！一大算法难点，加油加油！
回溯理论基础组合问题的剪枝操作
文档讲解：代码随想录回溯理论基础
视频讲解：回溯理论基础
回溯法也叫回溯搜索法，它是一种搜索，遍历的方式。回溯是递归的副产品，只要有递归就会有回溯，回溯本质就是递归过程中，到达底端（终止条件）后的不断返回过程。
回溯法的效率：回溯法的本质是穷举，它的效率并不高，是一种暴力解法，但有些时候我们就是需要这种暴力的解法，再适当增加剪枝解决问题。
回溯法解决的问题：回溯法，一般可以解决如下几种问题。
- 组合问题：N个数里面按一定规则找出k个数的集合。
- 切割问题：一个字符串按一定规则有几种切割方式。
- 子集问题：一个N个数的集合里有多少符合条件的子集。
- 排列问题：N个数按一定规则全排列，有几种排列方式。
- 棋盘问题：N皇后，解数独等等。
这些问题都不好解决，N值较小的情况还能够通过for循环进行遍历，但一旦N值增大，for循环就难以进行编写了，而且在我们无法确定要循环多少层的时候，也无法使用for循环。这个时候就需要使用回溯的方法递归的进行了。
回溯法的结构：回溯法解决的问题都可以抽象为n叉树的树形结构。例如在求集合的问题中，集合的大小就构成了树的宽度，递归的深度就构成了树的深度。因此在运用回溯法解题的时候，我们都可以通过画一个树状图来更好的理解递归的逻辑。
回溯法的模板：回溯法在进行编写的时候，主要需要注意三部，与递归三部曲相同的回溯三部曲。
- 回溯函数模板返回值以及参数：回溯算法中返回值一般为void，参数列表需要根据你的递归逻辑来一个个确定参数。
void backtracking(参数)- 回溯函数终止条件：即满足一定的条件，把答案存储下来，并结束本层递归。回溯函数中肯定需要有终止条件，不能陷入无止尽的递归，那样会导致栈溢出。因此回溯构成的树形结构一定是一个高度有限的树。
if (终止条件) {
存放结果;
return;
}- 回溯搜索的遍历过程：回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}for循环就是遍历集合区间，可以理解为一个节点有多少孩子，这个for循环就执行多少次。
backtracking这里自己调用自己，实现递归。从图中可以看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了。
总结模板如下：
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}
77.组合
文档讲解：代码随想录组合
视频讲解：手撕组合问题、
题目：
学习：本题是回溯算法的第一道题，也是利用回溯算法经典的题目之一。显然对于第一个示例n = 4，k = 2的情况来说，我们可以通过两个for循环很容易的就能得到所有的组合结果，但是当n，k不断增大，至少需要k个for循环才能够遍历所有的节点，直接进行顺序代码编写的时候根本无法进行，因此本题需要采用回溯算法，事实上就是通过递归的方式来进行for循环，本质就是一层递归就是一层for循环。用树形结构来解释本题的回溯过程，如下图：
代码：
//时间复杂度O(n*2^n)
//空间复杂度O(n)
class Solution {
public:
//设置全局变量，减少参数数量，避免引用
vector<vector<int>> result;
vector<int> path;
//确定回溯参数，由于是组合问题，组合中元素不存在顺序，因此还需要一个下标来指示当前遍历的位置
void backtracking (int n, int k, int idnex) {
//确定回溯终止条件
if(path.size() == k) {
result.push_back(path);
return;
}
//单层递归逻辑
for (int i = idnex; i <= n; i++) {
path.push_back(i);
backtracking(n, k, i + 1);
//回溯处理
path.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
backtracking(n, k, 1);
return result;
}
};本题还可以进行剪枝处理，显然上题中取4这一步是不需要的，因为已经构不成两个数了。当n=4，k=4中不需要的步骤会显得更多：
图中每一个节点就代表本层的for循环，剪枝的关键在于如何确定本层for循环的终点位置。
显然当for循环选择的位置之后的元素个数，不足我们需要的元素个数的时候，就没有必要搜索了。本题中已经选择的元素个数为path.size()，所需需要的元素个数为k - path.size()，列表中剩余元素个数(n - i)需要大于等于所需要的元素个数k - path.size()。因此i最多遍历到n - (k - path.size()) + 1的位置，也即 i <= n - (k - path.size()) + 1，为什么有个+1因为我们要把当前元素加上，这个通过例子模拟一下就能够理解。
因此优化后的for循环应该是：
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) // i为本次搜索的起始位置优化后的代码为：
class Solution {
public:
//设置全局变量，减少参数数量，避免引用
vector<vector<int>> result;
vector<int> path;
//确定回溯参数，由于是组合问题，组合中元素不存在顺序，因此还需要一个下标来指示当前遍历的位置
void backtracking (int n, int k, int idnex) {
//确定回溯终止条件
if(path.size() == k) {
result.push_back(path);
return;
}
//单层递归逻辑
for (int i = idnex; i <= n - (k - path.size()) + 1; i++) {
path.push_back(i);
backtracking(n, k, i + 1);
//回溯处理
path.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
backtracking(n, k, 1);
return result;
}
};总结：画图会更有助于我们进行算法的剪枝处理。
216.组合总和II
文档讲解：代码随想录组合总和III
视频讲解：手撕组合总和III
题目：
学习：本题与上题的不同在于遍历的集合确定了是1到9，n和k共同构成了遍历过程中需要判断的条件。本题中k相当于树的深度，9就是树的宽度，假如k=2，n=4用树形结构来表示就是：
代码： 回溯三部曲
//时间复杂度O(n*2^n)
//空间复杂度O(n)
class Solution {
public:
vector<vector<int>> result; // 存放结果集
vector<int> path; // 符合条件的结果
void backtracking(int n, int k, int val, int index) { //val已经收集的元素的总和，也就是path里元素的总和
//终止条件
if(path.size() == k) {
if(val == n) {
result.push_back(path);
}
return; // 如果path.size() == k 但sum != targetSum 直接返回
}
//单层递归逻辑
for(int i = index; i <= 9 - (k - path.size()) + 1; i++) {
val += i;
path.push_back(i);
backtracking(n, k, val, i + 1); //注意调整index遍历的集合范围
path.pop_back(); //回溯
val -= i; //回溯
}
}
vector<vector<int>> combinationSum3(int k, int n) {
backtracking(n, k, 0, 1);
return result;
}
};本题同样可以进行剪枝处理，例如上图中，后面有很大部分就不需要进行。
本题可以进行两部分的剪枝。1.首先适合上一道题相同的，依据k进行的集合大小的剪枝，也就是i只能遍历到9 - (k - path.size()) + 1；2.我们可以根据n进行剪枝，当加和val大于n的时候，就可以返回了，不需要继续进行集合后面数字的遍历，因为后面的数字加进来也一定会大于n，已经超出了我们所需要的值。
依据上述两点，代码进行剪枝处理后：
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
void backtracking(int n, int k, int val, int index) {
if(path.size() == k) {
if(val == n) {
result.push_back(path);
}
return;
}
//两个剪枝操作
//9 - (k - path.size()) + 1 对范围剪枝，不够k个元素就不用遍历
for(int i = index; i <= 9 - (k - path.size()) + 1; i++) {
val += i;
//值剪枝，大于n就不用遍历了
if(val > n) {
return;
}
path.push_back(i);
backtracking(n, k, val, i + 1);
path.pop_back();
val -= i;
}
}
vector<vector<int>> combinationSum3(int k, int n) {
backtracking(n, k, 0, 1);
return result;
}
};17.电话号码的字母组合
文档讲解：代码随想录电话号码的字母组合
视频讲解：手撕电话号码的字母组合
题目：
学习：显然本题也是一个不断循环匹配的过程。依据题干可以把本题分解为3步：1.拆分digits中的数字，并使数字与对应的字母串映射匹配；2.根据顺序依次进行循环遍历。3.保存结果集。例如依据”23“示例，我们可以给出回溯对应的树形图：
对于第1个问题，我们可以通过设置一个哈希表或者map来完成每个数字对字母串的映射，因为本题中数字数量有限且是顺序排列的，因此可以用一个数组来完成映射。
对于2，3问题，就是使用回溯算法来进行模拟遍历了。
代码： 确定回溯三部曲。
//时间复杂度: O(3^m * 4^n)，其中 m 是对应三个字母的数字个数，n 是对应四个字母的数字个数
//空间复杂度: O(3^m * 4^n)
class Solution {
private:
//使用一个数组来充当哈希表，对应每个字母
string letter[10] = {" ", " ", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
public:
vector<string> result;
string s;
//确定返回值和参数，参数中需要一个index来指示遍历到第几个数字了
void backtracking(string& digits, int index) {
//确定终止条件，当index--digits.size()时说明所有的数字都遍历完了，因为最后一个数字的下标为digits.size()-1
if(index == digits.size()) {
result.push_back(s);
return;
}
//取出数字对应的字符串
int dig = digits[index] - '0';
string list = letter[dig];
//确定单层递归逻辑
for(int i = 0; i < list.size(); i++) {
s.push_back(list[i]);
backtracking(digits, index + 1);
s.pop_back();
}
return; //可写可不写
}
vector<string> letterCombinations(string digits) {
if (digits.size() == 0) {
return result;
}
backtracking(digits, 0);
return result;
}
};总结：
回溯算法是一个不好理解的算法，初期过程中可以通过画树形图的方式来加深理解！
