代码随想录day22 | 回溯算法理论基础 leetcode 77.组合 77.组合 加剪枝操作 216.组合总和III 17.电话号码的字母组合
DAY22 回溯算法开始 学到目前最烧脑的一天
回溯算法理论基础
任何回溯算法都可以抽象成一个树结构
理论基础
什么是回溯法
回溯法也可以叫做回溯搜索法，它是一种搜索的方式。
在二叉树系列中，我们已经不止一次，提到了回溯
回溯是递归的副产品，只要有递归就会有回溯。
所以以下讲解中，回溯函数也就是递归函数，指的都是一个函数。
回溯法的效率
回溯法的性能如何呢，这里要和大家说清楚了，虽然回溯法很难，很不好理解，但是回溯法并不是什么高效的算法。
因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。
那么既然回溯法并不高效为什么还要用它呢？
因为没得选，一些问题能暴力搜出来就不错了，撑死了再剪枝一下，还没有更高效的解法。
此时大家应该好奇了，都什么问题，这么牛逼，只能暴力搜索。
回溯法解决的问题
回溯法，一般可以解决如下几种问题：
- 组合问题：N个数里面按一定规则找出k个数的集合
- 切割问题：一个字符串按一定规则有几种切割方式
- 子集问题：一个N个数的集合里有多少符合条件的子集
- 排列问题：N个数按一定规则全排列，有几种排列方式
- 棋盘问题：N皇后，解数独等等
相信大家看着这些之后会发现，每个问题，都不简单！
另外，会有一些同学可能分不清什么是组合，什么是排列？
组合是不强调元素顺序的，排列是强调元素顺序。
例如：{1, 2} 和 {2, 1} 在组合上，就是一个集合，因为不强调顺序，而要是排列的话，{1, 2} 和 {2, 1} 就是两个集合了。
记住组合无序，排列有序，就可以了。
如何理解回溯法
回溯法解决的问题都可以抽象为树形结构，是的，我指的是所有回溯法的问题都可以抽象为树形结构！
因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度就构成了树的深度。
递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。
回溯算法的基本思路：
- 选择：在当前状态下，尝试所有可能的选择。
- 约束：在做出选择后，检查当前选择是否满足问题的约束条件。
- 撤销：如果选择不满足条件或达到最终状态，则撤销该选择（回溯）。
- 终止条件：到达目标状态时，记录解或停止递归。
回溯算法框架 !!!
典型的伪代码如下：
void backtrack(参数) {
if (满足结束条件) {
保存结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果 即与处理节点为相反操作
}
回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。
for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。
backtracking这里自己调用自己，实现递归。
大家可以从图中看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了。
77.组合
Java：
未剪枝优化
class Solution {
List<List<Integer>> result = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>(); //因为要进行删除末尾的操作,(pop) 所以用LikedList
public List<List<Integer>> combine(int n, int k) {
backtracking(n, k, 1);
return result;
}
public void backtracking(int n, int k, int startIndex) {
if(path.size() == k) { // 递归终止条件：当前路径已经满足目标长度
result.add(new ArrayList<> (path)); // 保存当前路径
return;
}
for(int i = startIndex; i <= n; i++) { // 遍历当前范围的数字
path.add(i); // 选择数字 i，加入到路径
backtracking(n, k, i + 1); // 递归，选择下一个数字，因为要求是组合,不能有重复,所以范围从 i+1 开始
path.removeLast(); // 回溯，撤销当前选择
}
}
}
回溯思想解析
- 选择：
- 在
for循环中，依次选择一个数字加入到当前路径path中。 - 每次选择后，进入下一层递归，继续选择下一个数字。
- 在
- 递归：
- 递归的过程就是尝试不同数字组合的过程。
- 通过更新
startIndex，确保每次选择不会重复（如[1, 2]和[2, 1]只会生成一次）。
- 回溯：
- 如果当前路径长度达到了目标长度（
path.size() == k），将其保存到结果集后，回溯到上一步。 - 回溯通过
path.removeLast()撤销最后一次选择，尝试其他可能性。
- 如果当前路径长度达到了目标长度（
77.组合 加剪枝操作
此剪枝是for里面的边界控制
java
class Solution {
List<List<Integer>> result = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> combine(int n, int k) {
backtracking(n, k, 1);
return result;
}
public void backtracking(int n, int k, int startIndex) {
if(path.size() == k) {
result.add(new ArrayList<> (path));
return;
}
for(int i = startIndex; i <= n - (k - path.size()) + 1; i++) {
path.add(i);
backtracking(n, k, i + 1);
path.removeLast();
}
}
}
n - (k - path.size()) + 1 的含义
背景
我们的问题是从 1 到 n 中选择 k 个数字组成组合。path 是我们当前已经选择的数字，path.size() 代表当前选择的数字个数。
n是总数字的范围（从 1 到 n）。k是我们需要选择的数字个数。path.size()是我们当前已经选择的数字个数。k - path.size()是我们还需要选择的数字个数。
剪枝的目标
我们希望在遍历时剪去那些不可能组成有效组合的分支。比如，如果剩下的数字不足以组成一个长度为 k 的组合，就停止递归，避免不必要的计算。
n - (k - path.size()) + 1 的含义
假设当前选择的数字已经有 path.size() 个，还需要选择 k - path.size() 个数字。此时，剩下的可选数字从当前位置 i 开始，最多有多少个数字可以用来构成组合呢？
1. 剩余需要选择的数字个数：
- 当前已经选择的数字是
path.size()。 - 我们还需要选择
k - path.size()个数字。
这意味着，从当前位置 i 开始，我们必须确保剩下的数字至少有 k - path.size() 个，才能继续构成有效的组合。
2. 剩余数字的总数：
假设当前位置是 i，那么从 i 开始，到 n 的数字有多少个呢？这个数字的数量是 n - i + 1（从 i 到 n 包括 i 本身）。
3. 限制条件：
为了保证我们能够从当前位置 i 开始选择，剩余的数字总数必须至少是我们需要选择的数字个数，即 k - path.size()。
所以，剩余的数字个数应该满足：
n - i + 1 >= k - path.size()
调整顺序得
i <= n - (k - path.size()) + 1
216.组合总和III
Java
class Solution {
//因为只使用数字1到9,所以[1, n]n变成了9 边界控制就变成了9 - (k - path.size()) + 1
List<List<Integer>> result = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> combinationSum3(int k, int n) {
backtracking(n, k, 0, 1); //n含义trageSum k含义path.size 0含义sum 1含义startIndex
return result;
}
public void backtracking(int trageSum, int k, int sum, int startIndex) {
if(sum > trageSum) return;
if(path.size() == k){
if(sum == trageSum) {
result.add(new ArrayList<>(path));
}
return;
}
for(int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {
sum += i;
path.add(i);
backtracking(trageSum, k, sum , i + 1);
sum -= i;//可以不写 因为 Java 的基本类型是按值传递的，sum 在递归调用中已经发生了变化，不需要显式地恢复。
path.removeLast();
}
}
}
这道题中剪枝操作除了边界处理i <= 9 - (k - path.size()) + 1还有if(sum > trageSum) return
17.电话号码的字母组合
Java
class Solution {
//设置全局列表存储最后的结果
List<String> list = new ArrayList<>();
public List<String> letterCombinations(String digits) {
if (digits == null || digits.length() == 0) {
return list;
}
//初始对应所有的数字，为了直接对应2-9，新增了两个无效的字符串""
String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
//迭代处理
backTracking(digits, numString, 0);
return list;
}
//每次迭代获取一个字符串，所以会涉及大量的字符串拼接，所以这里选择更为高效的 StringBuilder
StringBuilder temp = new StringBuilder();
//比如digits如果为"23",num 为0，则str表示2对应的 abc
public void backTracking(String digits, String[] numString, int num) {
//遍历全部一次记录一次得到的字符串
if (num == digits.length()) {
list.add(temp.toString());
return;
}
//str 表示当前num对应的字符串
String str = numString[digits.charAt(num) - '0'];
for (int i = 0; i < str.length(); i++) {
temp.append(str.charAt(i));
//递归，处理下一层
backTracking(digits, numString, num + 1);
//剔除末尾的继续尝试
temp.deleteCharAt(temp.length() - 1);
}
}
}
str.charAt(i)：这个方法用于从字符串str中获取索引为i的字符。str是当前数字对应的字母字符串（例如，如果当前处理的是数字2，则str = "abc"）。charAt(i)会返回该字符串中的第i个字符，比如str.charAt(0)会返回字符'a'，str.charAt(1)会返回字符'b'，依此类推。temp.append(...)：append是StringBuilder的方法，用于将参数（此处是字符）添加到StringBuilder对象temp的末尾。StringBuilder是一个可变的字符串构建工具，可以高效地处理字符串的拼接操作。