目录
一、回溯算法介绍
什么是回溯算法
回溯算法的模板
二、实践
1、题目链接
2、题目
3、解法(回溯+剪枝)
1）优先画出决策树
4、代码
一、回溯算法介绍
什么是回溯算法
回溯算法是⼀种经典的递归算法，通常用于解决组合问题、排列问题和搜索问题等。
回溯算法的基本思想：从⼀个初始状态开始，按照⼀定的规则向前搜索，当搜索到某个状态⽆法前进时，回退到前⼀个状态，再按照其他的规则搜索。
回溯算法在搜索过程中维护⼀个状态树，通过遍历状态树来实现对所有可能解的搜索。
回溯算法的核心思想：“试错”，即在搜索过程中不断地做出选择，如果选择正确，则继续向前搜 索；否则，回退到上⼀个状态，重新做出选择。回溯算法通常⽤于解决具有多个解，且每个解都需要 搜索才能找到的问题。
回溯算法的模板
void backtrack(vector<int>& path, vector<int>& choice, ...) {// 满⾜结束条件if (/* 满⾜结束条件 */) {// 将路径添加到结果集中res.push_back(path);return;}// 遍历所有选择for (int i = 0; i < choices.size(); i++) {// 做出选择path.push_back(choices[i]);// 做出当前选择后继续搜索backtrack(path, choices);// 撤销选择path.pop_back();}
}
其中， path 表示当前已经做出的选择， choices 表示当前可以做的选择。
在回溯算法中，我们需要做出选择，然后递归地调⽤回溯函数。
如果满足结束条件，则将当前路径添加到结果集中；否则， 我们需要撤销选择，回到上⼀个状态，然后继续搜索其他的选择。
回溯算法的时间复杂度通常较⾼，因为它需要遍历所有可能的解。但是，回溯算法的空间复杂度较 低，因为它只需要维护⼀个状态树。
在实际应⽤中，回溯算法通常需要通过剪枝等方法进行优化，以减少搜索的次数，从而提高算法的效率。
对于我们解题最重要的就是画出决策树，把所有情况的详细的列出来。根据决策树，进行不同方面的消息。
二、实践
1、题目链接
46.全排列（LeetCode）
2、题目
3、解法(回溯+剪枝)
1）优先画出决策树
越详细越好
2）设计代码
仔细观察决策树。
围绕三个主要的方面进行考虑：全局变量、dfs 函数、细节（回溯、剪枝）
- 全局变量
//全局变量vector<vector<int>> ans; //结果集vector<int> path; //走过的路径bool check[7]; //剪枝数组
- dfs 函数
仅需关心，某一个结点在干什么事情
- 细节问题
回溯
1. 干掉 path 最后一个元素
2.修改 check 数组
剪枝
递归出口遇到叶子结点的时候，直直接添加结果
4、代码
class Solution {//回溯+剪枝+dfs//全局变量vector<vector<int>> ans; //结果集vector<int> path; //走过的路径bool check[7]; //剪枝数组public://深搜void dfs(vector<int>& nums){//出口---叶子结点,走过的路径==nums.sizeif (path.size() == nums.size()){//更新结果集ans.push_back(path);return;}//对数组开始循环遍历for (int i = 0; i < nums.size(); i++){//剪枝if (!check[i]) //尚未被选择{check[i] = true; //更新path.push_back(nums[i]); //path更新dfs(nums); //继续深搜path.pop_back(); //回溯，更新pathcheck[i] = false; //恢复}}}vector<vector<int>> permute(vector<int>& nums) {dfs(nums);return ans;}
};
