代码随想录刷题day22丨回溯理论基础，77. 组合，216.组合总和III，17.电话号码的字母组合

1.回溯理论基础

1.1题目分类

在这里插入图片描述

1.2什么是回溯法

回溯法也可以叫做回溯搜索法，它是一种搜索的方式。
回溯是递归的副产品，只要有递归就会有回溯。
回溯函数也就是递归函数，指的都是一个函数。

1.3回溯法的效率

虽然回溯法很难，很不好理解，但是回溯法并不是什么高效的算法。
因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。
那么既然回溯法并不高效为什么还要用它呢？
- 因为没得选，一些问题能暴力搜出来就不错了，撑死了再剪枝一下，还没有更高效的解法。

1.4回溯法解决的问题

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

1.5如何理解回溯法

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

1.6回溯法模版（回溯三部曲）

回溯函数模板返回值以及参数
- 在回溯算法中，我的习惯是函数起名字为backtracking，这个起名大家随意。
- 回溯算法中函数返回值一般为void。
- 再来看一下参数，因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数。
```
void backtracking(参数)
```
回溯函数终止条件
- 既然是树形结构，就知道遍历树形结构一定要有终止条件。所以回溯也有要终止条件。
- 什么时候达到了终止条件，树中就可以看出，一般来说搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。
```
if (终止条件) {存放结果;return;
}
```
回溯搜索的遍历过程
- 在上面我们提到了，回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。
- 集合大小和孩子的数量是相等的！
```
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {处理节点;backtracking(路径，选择列表); // 递归回溯，撤销处理结果
}
```
- for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。
  
  backtracking这里自己调用自己，实现递归。
- 图示
- 从图中看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了

分析完过程，回溯算法模板框架如下：

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

注意：这份模板很重要，后面做回溯法的题目都靠它了！

2.题目

2.1组合

题目链接：77. 组合 - 力扣（LeetCode）
视频讲解：带你学透回溯算法-组合问题（对应力扣题目：77.组合）| 回溯法精讲！_哔哩哔哩_bilibili
文档讲解：https://programmercarl.com/0077.%E7%BB%84%E5%90%88.html
解题思路：
- 要解决 n为100，k为50的情况，暴力写法需要嵌套50层for循环，那么回溯法就用递归来解决嵌套层数的问题。
- 递归来做层叠嵌套（可以理解是开k层for循环），每一次的递归中嵌套一个for循环，那么递归就可以用于解决多层嵌套循环的问题了。
- 此时递归的层数大家应该知道了，例如：n为100，k为50的情况下，就是递归50层。
- 回溯法解决的问题都可以抽象为树形结构（N叉树），用树形结构来理解回溯就容易多了。
- 那么我把组合问题抽象为如下树形结构：
  - 可以看出这棵树，一开始集合是 1，2，3，4，从左向右取数，取过的数，不再重复取。
    
    第一次取1，集合变为2，3，4 ，因为k为2，我们只需要再取一个数就可以了，分别取2，3，4，得到集合[1,2] [1,3] [1,4]，以此类推。
  - 每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围。
  - 图中可以发现n相当于树的宽度，k相当于树的深度。
  - 那么如何在这个树上遍历，然后收集到我们要的结果集呢？
    - 图中每次搜索到了叶子节点，我们就找到了一个结果。
    - 相当于只需要把达到叶子节点的结果收集起来，就可以求得 n个数中k个数的组合集合。
- 回溯法三部曲
  - 递归函数的返回值以及参数
    - 在这里要定义两个全局变量，一个用来存放符合条件单一结果，一个用来存放符合条件结果的集合。
    - 代码如下：
```
List<List<Integer>> result;//存放符合条件结果的集合
List<Integer> path;//存放符合条件单一结果
```
    - 其实不定义这两个全局变量也是可以的，把这两个变量放进递归函数的参数里，但函数里参数太多影响可读性，所以我定义全局变量了。
    - 函数里一定有两个参数，既然是集合n里面取k个数，那么n和k是两个int型的参数。
    - 然后还需要一个参数，为int型变量startIndex，这个参数用来记录本层递归的中，集合从哪里开始遍历（集合就是[1,…,n] ）。
    - 为什么要有这个startIndex呢？
      - startIndex 就是防止出现重复的组合。
      - 从下图中红线部分可以看出，在集合[1,2,3,4]取1之后，下一层递归，就要在[2,3,4]中取数了，那么下一层递归如何知道从[2,3,4]中取数呢，靠的就是startIndex。
      - 所以需要startIndex来记录下一层递归，搜索的起始位置。
    - 那么整体代码如下：
```
List<List<Integer>> result = new ArrayList<>();//存放符合条件结果的集合
List<Integer> path = new ArrayList<>();//存放符合条件单一结果
void backtracking(int n,int k,int startIndex)
```
  - 回溯函数终止条件
    - 什么时候到达所谓的叶子节点了呢？
      - path这个数组的大小如果达到k，说明我们找到了一个子集大小为k的组合了，在图中path存的就是根节点到叶子节点的路径。
      - 如图红色部分：
      - 此时用result二维数组，把path保存起来，并终止本层递归。
    - 所以终止条件代码如下：
```
if(path.size() == k){result.add(new ArrayList<>(path));// 深拷贝 path 并添加到 resultreturn;
}
```
  - 单层搜索的过程
    - 回溯法的搜索过程就是一个树型结构的遍历过程，在如下图中，可以看出for循环用来横向遍历，递归的过程是纵向遍历。
    - for循环每次从startIndex开始遍历，然后用path保存取到的节点i。
    - 代码如下：
```
for(int i = startIndex;i <= n;i++){// 控制树的横向遍历path.add(i);// 处理节点backtracking(n,k,i + 1);// 递归：控制树的纵向遍历，注意下一层搜索要从i+1开始path.remove(path.size() -1);// 回溯，撤销处理的节点
}
```
    - 可以看出backtracking（递归函数）通过不断调用自己一直往深处遍历，总会遇到叶子节点，遇到了叶子节点就要返回。
    - backtracking的下面部分就是回溯的操作了，撤销本次处理的结果。

代码：

class Solution {List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合List<Integer> path = new ArrayList<>();// 存放符合条件单一结果public List<List<Integer>> combine(int n, int k) {backtracking(n, k, 1);return result;}void backtracking(int n, int k, int startIndex) {if (path.size() == k) {result.add(new ArrayList<>(path));// 深拷贝 path 并添加到 resultreturn;}for (int i = startIndex; i <= n; i++) {// 控制树的横向遍历path.add(i);// 处理节点backtracking(n, k, i + 1);// 递归：控制树的纵向遍历，注意下一层搜索要从i+1开始path.remove(path.size() - 1);// 回溯，撤销处理的节点}}
}

可以对代码做剪枝优化
- 剪枝视频讲解：带你学透回溯算法-组合问题的剪枝操作（对应力扣题目：77.组合）| 回溯法精讲！_哔哩哔哩_bilibili
- 优化过程如下：
  1. 已经选择的元素个数：path.size();
  2. 还需要的元素个数为: k - path.size();
  3. 在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历
- 所以优化之后的for循环是：
```
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) // i为本次搜索的起始位置
```

剪枝优化代码：

class Solution {List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合List<Integer> path = new ArrayList<>();// 存放符合条件单一结果public List<List<Integer>> combine(int n, int k) {backtracking(n, k, 1);return result;}void backtracking(int n, int k, int startIndex) {if (path.size() == k) {result.add(new ArrayList<>(path));// 深拷贝 path 并添加到 resultreturn;}for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) {// 控制树的横向遍历path.add(i);// 处理节点backtracking(n, k, i + 1);// 递归：控制树的纵向遍历，注意下一层搜索要从i+1开始path.remove(path.size() - 1);// 回溯，撤销处理的节点}}
}

总结：
- 组合问题是回溯法解决的经典问题，我们开始的时候给大家列举一个很形象的例子，就是n为100，k为50的话，直接想法就需要50层for循环。
- 从而引出了回溯法就是解决这种k层for循环嵌套的问题。
- 然后进一步把回溯法的搜索过程抽象为树形结构，可以直观的看出搜索的过程。
- 接着用回溯法三部曲，逐步分析了函数参数、终止条件和单层搜索的过程

2.2组合总和III

题目链接：216. 组合总和 III - 力扣（LeetCode）
视频讲解：和组合问题有啥区别？回溯算法如何剪枝？| LeetCode：216.组合总和III_哔哩哔哩_bilibili
文档讲解：https://programmercarl.com/0216.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CIII.html
解题思路：回溯
- 例如 k = 2，n = 4的话，就是在集合[1,2,3,4,5,6,7,8,9]中求 k（个数） = 2, n（和） = 4的组合。
- 定义path 和 result为全局变量。
- targetSum（int）目标和，也就是题目中的n。
- k（int）就是题目中要求k个数的集合。
- sum（int）为已经收集的元素的总和，也就是path里元素的总和。
- startIndex（int）为下一层for循环搜索的起始位置。
- k其实就已经限制树的深度，因为就取k个元素，树再往下深了没有意义。

代码：

class Solution {List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合List<Integer> path = new ArrayList<>();// 存放符合条件单一结果public List<List<Integer>> combinationSum3(int k, int n) {backtracking(n,k,0,1);return result;}void backtracking(int targetSum, int k, int sum, int startIndex){if(sum > targetSum){return;}if(path.size() == k){if(targetSum == sum){result.add(new ArrayList<>(path));return;}}for(int i = startIndex;i <= 9;i++){path.add(i);sum += i;backtracking(targetSum,k,sum,i + 1);sum -= i;path.remove(path.size() -1);}}
}//剪枝优化
class Solution {List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合List<Integer> path = new ArrayList<>();// 存放符合条件单一结果public List<List<Integer>> combinationSum3(int k, int n) {backtracking(n,k,0,1);return result;}void backtracking(int targetSum, int k, int sum, int startIndex){if(sum > targetSum){//剪枝return;}if(path.size() == k){if(targetSum == sum){result.add(new ArrayList<>(path));return;}}for(int i = startIndex;i <= 9 - (k - path.size()) + 1;i++){//剪枝path.add(i);sum += i;backtracking(targetSum,k,sum,i + 1);sum -= i;//回溯path.remove(path.size() -1);//回溯}}
}

总结：
- 处理过程就是 path收集每次选取的元素，相当于树型结构里的边，sum来统计path里元素的总和。
- 别忘了处理过程和回溯过程是一一对应的，处理有加，回溯就要有减！
- 把问题抽象为树形结构，按照回溯三部曲进行讲解，最后给出剪枝的优化。

2.3电话号码的字母组合

题目链接：17. 电话号码的字母组合 - 力扣（LeetCode）
视频讲解：还得用回溯算法！| LeetCode：17.电话号码的字母组合_哔哩哔哩_bilibili
文档讲解：https://programmercarl.com/0017.%E7%94%B5%E8%AF%9D%E5%8F%B7%E7%A0%81%E7%9A%84%E5%AD%97%E6%AF%8D%E7%BB%84%E5%90%88.html
解题思路：回溯
- 例如：输入：“23”，抽象为树形结构，如图所示：
- 回溯三部曲：
  - 确定回溯函数参数
    - 首先需要一个字符串temp来收集叶子节点的结果，然后用一个字符串数组result保存起来，这两个变量我依然定义为全局。
    - 再来看参数，参数指定是有题目中给的string digits，然后还要有一个参数就是int型的index。
    - 这个index是记录遍历第几个数字了，就是用来遍历digits的（题目中给出数字字符串），同时index也表示树的深度。
    - 代码如下：
```
StringBuilder temp = new StringBuilder();
List<String> result = new ArrayList<>();
```
  - 确定终止条件
    - 例如输入用例"23"，两个数字，那么根节点往下递归两层就可以了，叶子节点就是要收集的结果集。
      
      那么终止条件就是如果index 等于输入的数字个数（digits.size）了（本来index就是用来遍历digits的）。
      
      然后收集结果，结束本层递归。
    - 代码如下：
```
if(index == digits.length()){result.add(temp.toString());return;
}
```
  - 确定单层遍历逻辑
    - 首先要取index指向的数字，并找到对应的字符集（手机键盘的字符集）。
      
      然后for循环来处理这个字符集，代码如下：
```
int digit = digits.charAt(index) - '0';
String letter = numString[digit];
for(int i = 0;i < letter.length();i++){temp.append(letter.charAt(i));backtracking(digits,index + 1);temp.deleteCharAt(temp.length() -1);
}
```
    - 注意：输入1 * #按键等等异常情况
      
      代码中最好考虑这些异常情况，但题目的测试数据中应该没有异常情况的数据，所以我就没有加了。
      
      但是要知道会有这些异常，如果是现场面试中，一定要考虑到！

代码：

class Solution {StringBuilder temp = new StringBuilder();List<String> result = new ArrayList<>();//初始对应所有的数字，为了直接对应2-9，新增了两个无效的字符串""String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};public List<String> letterCombinations(String digits) {if(digits == null || digits.length() == 0){return result;}backtracking(digits,0);return result;}void backtracking(String digits,int index){if(index == digits.length()){result.add(temp.toString());return;}int digit = digits.charAt(index) - '0';String letter = numString[digit];for(int i = 0;i < letter.length();i++){temp.append(letter.charAt(i));backtracking(digits,index + 1);temp.deleteCharAt(temp.length() -1);}}
}

总结：
- StringBuilder 是可变的，因此可以高效地进行添加和删除操作。
- String 是不可变的，无法直接对其进行修改。
- String对象 = StringBuild对象.toString();
- 计算长度总结：
  - length：字符串、数组
  - size：栈（Stack）、队列（Queue）、ArrayList、HashSet、HasnMap