第七章 回溯算法part01
理论基础
重点摘录
- 回溯法解决的问题都可以抽象为树形结构，是的，我指的是所有回溯法的问题都可以抽象为树形结构！
- 因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度就构成了树的深度。
- 递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。
回溯法模板
- 返回值和参数：返回值一般是void，参数一般是写完逻辑再确定
- 终止条件：看题意决定，一般是找到了符合条件的叶子节点。
回溯法模板伪代码：
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}
77. 组合
- 对着 在 回溯算法理论基础 给出的 代码模板，来做本题组合问题，大家就会发现 写回溯算法套路。
- 本题关于剪枝操作是大家要理解的重点，因为后面很多回溯算法解决的题目，都是这个剪枝套路。
思路
- 组合不强调顺序，排列强调顺序。
- 暴力解法就是有多少k就要嵌套多少for循环。回溯算法本质上也是穷举，但是通过递归有多少for循环。
-
回溯算法搜素的过程：
示例
伪代码实现：
// 一个组合就是一个一维数组，结果集就是一个二维数组
// 用来存放符合条件结果
private List<Integer> path = new ArrayList<>();
// 存放符合条件结果的集合
private List<List<Integer>> result = new ArrayList<>();
//递归的参数及返回值
//startIndex 每次搜索的起始位置，初始位置是1
private void backtracking(int n, int k, int startIndex){
//确定终止条件：到叶子节点
if(path.size() == k){
result.add(new ArrayList<>(path));
return;
}
//单层递归的逻辑：每一个节点都是for循环
for(i=startIndex; i<=n; i++){
path.add(i);
backtracking(n, k, i+1);
path.remove(path.size() - 1); //比如，12之后是13，要把2弹出，把3加进来，才能得到13
}
}
这道题还可以做剪枝
比如n=4，k=4，在{2,x,x,x}的分支下，一共只剩下3个元素（234），怎么也不可能出现k=4的情况，所以就可以做剪枝，{3,x,x,x}（只剩下元素34），{4,x,x,x}（只剩下元素4）也是一样的。
原来的代码
private void backtracking(int n, int k, int startIndex){
……
//单层逻辑
for(i=startIndex; i<=n; i++){
path.add(i);
backtracking(n, k, i+1); //递归可以理解为，沿着节点的树形结构往下搜索的过程。i可以理解为每个节点的子孩子。我们要剪枝的就是一些节点的子孩子。
path.remove(path.size() - 1);
}
path可以理解为要选择的元素，k-path.size()
就是还需要选取的元素的个数。还需要选取的元素个数，至多开始的位置=(k-path.size()) + 1，+1是因为要包含起始位置
class Solution {
private List<Integer> path = new ArrayList<>();
private List<List<Integer>> result = new ArrayList<>();
private 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.remove(path.size()-1);
}
}
public List<List<Integer>> combine(int n, int k) {
result.clear();
path.clear();
backtracking(n, k, 1);
return result;
}
}
216.组合总和III
思路
- 回溯算法，for循环里嵌套回溯算法，用递归的方式实现。
-
抽象成树形结构（任何回溯算法都可以抽象为树形结构）。
来源：代码随想录
伪代码
path（一维数组）
result（二维数组）
void backtracking(int targetSum, int k, int sum, int startIndex){
if(sum > targetSum) return; //剪枝1
//终止条件
if(path.size() == k){
if(targetSum == sum) result.add(new ArrayList<>(path));
return;
}
//单层搜索逻辑
//for(int i = startIndex; i <= 9; i++){ //可以剪枝
for(int i = startIndex; i <= 9-(k-path.size())+1; i++){
sum += i;
path.add(i);
backtracking(targetSum, k, sum, i + 1);
sum -= i;
path.remove(path.size()-1);
}
}
class Solution {
private List<List<Integer>> result = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
private void backtracking(int sum, int k, int targetSum, int startIndex){
if(sum > targetSum) return;
if(path.size() == k){
if(sum == targetSum) result.add(new ArrayList<>(path));
return;
}
for(int i = startIndex; i <= 9 - (k - path.size()) + 1; i++){ //注意这里是<=
sum += i;
path.add(i);
backtracking(sum, k, targetSum, i+1);
sum -= i;
//path.remove(path.size()-1); 可以用下面这个方法
path.removeLast();
}
}
public List<List<Integer>> combinationSum3(int k, int n) {
result.clear();
path.clear();
backtracking(0, k, n, 1);
return result;
}
}
17.电话号码的字母组合
题目链接/文章讲解
本题大家刚开始做会有点难度，先自己思考20min，没思路就直接看题解。
思路
- 使用map或者二维数组做映射
private static final String[] letterMap = {
"", // 0
"", // 1
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs",// 7
"tuv", // 8
"wxyz" // 9
};
图示
树的深度：输入数字的个数
树的宽度：每个数字对应的字母
cr：代码随想录
伪代码
private List<String> result = new ArrayList<>();
private StringBuilder s = new StringBuilder();
private void backtracking(String digits, int index) { //index 是递归中传入的字符串遍历到哪一个数字了
if(index == digits.length()){
result.add(s.toString());
return;
}
//单层遍历结果
int digit = digits.charAt(index) - '0'; // 将index指向的数字转为int
String letters = letterMap[digit];
for(int i = 0; i < letters.length(); i++){
s.append(letters.chatAt(i)); //把letters中对应的字母放进来
backtracking(digits, index + 1);
s.deleteCharAt(s.length() - 1);
//如果把回溯隐藏在参数中就是：
//void getCombinations(const string& digits, int index, const string& s)
//getCombinations(digits, index + 1, s + letters[i]);
}
}
public List<String> letterCombinations(String digits) {
result.clear();
s.setLength(0); // 清空StringBuilder
if (digits.length() == 0) {
return result;
}
backtracking(digits, 0);
return result;
}
class Solution {
private String[] letterMap = {
"", // 0
"", // 1
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs",// 7
"tuv", // 8
"wxyz" // 9
};
private List<String> result = new ArrayList<>();
private StringBuilder s = new StringBuilder();
private void backtracking(String digits, int index){
if(index == digits.length()){
result.add(s.toString());
return;
}
int digit = digits.charAt(index) - '0';
String letters = letterMap[digit];
for(int i = 0; i < letters.length(); i++){
s.append(letters.charAt(i));
backtracking(digits, index+1);
s.deleteCharAt(s.length() - 1);
}
}
public List<String> letterCombinations(String digits) {
result.clear();
s.setLength(0);
if (digits.length() == 0) {
return result;
}
backtracking(digits, 0);
return result;
}
}
