代码随想录25 回溯算法
目录
回溯算法：
（1）回溯算法可以解决以下的问题：
（2）一般模板：
77.组合
216.组合总和lll
17.电话号码的字母组合
106.从中序与后序遍历序列构造二叉树
(1) 前序 + 中序 或 后序 + 中序
(2) 前序 + 后序
回溯算法：
回溯和递归是相辅相成的，回溯常常是写在递归函数里的
递归其实是一种暴力搜索
（1）回溯算法可以解决以下的问题：
1.组合
2.切割
3.子集
4.排列
5.棋盘
（2）一般模板：
void backtracking(参数）{
if(终止条件){
收集结果；
return;
}
for(集合元素){
处理结点；
递归函数；
回溯操作；
}
return
}77.组合
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1：
输入：n = 4, k = 2 输出： [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
class Solution {
public:
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> result; // 存储最终结果
vector<int> path; // 当前路径
backtracking(n, k, 1, path, result); // 从 1 开始遍历
return result;
}
private:
void backtracking(int n, int k, int startIndex, vector<int>& path, vector<vector<int>>& result) {
// 判断终止条件
if (path.size() == k) {
result.push_back(path); // 保存当前路径到结果集
return;
}
for (int i = startIndex; i <= n; i++) { // 遍历从 startIndex 到 n
path.push_back(i); // 选择当前数字
backtracking(n, k, i + 1, path, result); // 递归到下一层
path.pop_back(); // 回溯，撤销选择
}
}
};
优化，剪枝后
剪枝就是将后面无法实现的情况直接不用考虑了
一般是在i的循环条件中改变最大的取值条件
for (int i = startIndex; i <= n-(k-path.size())+1; i++)216.组合总和lll
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
- 只使用数字1到9
- 每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
示例 1:
输入: k = 3, n = 7 输出: [[1,2,4]] 解释: 1 + 2 + 4 = 7 没有其他符合的组合了。
class Solution {
public:
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> result; // 存储最终结果
vector<int> path; // 当前路径
backtracking(k, n, 1, 0, path, result); // 从 1 开始遍历
return result;
}
private:
void backtracking(int k, int n, int startIndex, int sum, vector<int>& path, vector<vector<int>>& result) {
// 判断终止条件
if (path.size() == k) {
if (sum == n) { // 如果路径长度为 k 且当前和等于目标值
result.push_back(path);
}
return;
}
// 剪枝优化：如果剩余的数字不够填满路径，直接返回
for (int i = startIndex; i <= 9 ; i++) {
path.push_back(i); // 选择当前数字
backtracking(k, n, i + 1, sum + i, path, result); // 递归到下一层,在这里进行sum与startindex的操作
path.pop_back(); // 回溯，撤销选择
}
}
};
剪枝优化后：
for (int i = startIndex; i <= 9 - (k - path.size()) + 1 ; i++) 17.电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
代码如下：
class Solution {
public:
vector<string> letterCombinations(string digits) {
if (digits.empty()) return {}; // 输入为空，直接返回空结果
// 数字到字母的映射表
vector<string> letterMap = {
"", // 0
"", // 1
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs",// 7
"tuv", // 8
"wxyz" // 9
};
vector<string> result; // 存储结果
string path; // 当前路径
backtracking(digits, 0, path, result, letterMap);
return result;
}
private:
void backtracking(string digits, int index, string& path, vector<string>& result, const vector<string>& letterMap) {
// 终止条件
if (index == digits.size()) {
result.push_back(path); // 保存当前路径到结果集
return;
}
int digit = digits[index] - '0'; // 将字符转换为整数
const string& letter = letterMap[digit]; // 获取对应的字母字符串
// 遍历字母
for (char ch : letter) {
path.push_back(ch); // 选择当前字母
backtracking(digits, index + 1, path, result, letterMap); // 递归下一层
path.pop_back(); // 回溯，撤销选择
}
}
};
106.从中序与后序遍历序列构造二叉树
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
注：仅知道前序、中序或后序中的任何一个遍历结果，无法唯一确定一棵二叉树的结构。
(1) 前序 + 中序 或 后序 + 中序
这些组合可以唯一确定树的结构，因为：
- 中序遍历给出了左右子树的分界点。
- 前序或后序遍历给出了根节点和访问顺序。
(2) 前序 + 后序
单独的 前序 + 后序 也无法唯一确定树的结构，因为左右子树的分界点未知。
思路：
1.后序数组为0，空结点
2.后序数组最后一个元素为根节点元素
3.寻找中序数组位置作切割点
4.切中序数组
5.切后序数组
6.递归处理
class Solution {
private:
TreeNode* traversal (vector<int>& inorder, vector<int>& postorder) {
if (postorder.size() == 0) return NULL;
// 后序遍历数组最后一个元素，就是当前的中间节点
int rootValue = postorder[postorder.size() - 1];
TreeNode* root = new TreeNode(rootValue);
// 叶子节点
if (postorder.size() == 1) return root;
// 找到中序遍历的切割点
int delimiterIndex;
for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {
if (inorder[delimiterIndex] == rootValue) break;
}
// 切割中序数组
// 左闭右开区间：[0, delimiterIndex)
vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
// [delimiterIndex + 1, end)
vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() );
// postorder 舍弃末尾元素
postorder.resize(postorder.size() - 1);
// 切割后序数组
// 依然左闭右开，注意这里使用了左中序数组大小作为切割点
// [0, leftInorder.size)
vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
// [leftInorder.size(), end)
vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());
root->left = traversal(leftInorder, leftPostorder);
root->right = traversal(rightInorder, rightPostorder);
return root;
}
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (inorder.size() == 0 || postorder.size() == 0) return NULL;
return traversal(inorder, postorder);
}
};