1. 什么是回溯算法
回溯算法是⼀种经典的递归算法，通常用于解决组合问题、排列问题和搜索问题等。
回溯算法的基本思想：从一个初始状态开始，按照⼀定的规则向前搜索，当搜索到某个状态⽆法前进时，回退到前⼀个状态，再按照其他的规则搜索。回溯算法在搜索过程中维护一个状态树，通过遍历状态树来实现对所有可能解的搜索。
回溯算法的核心思想：“试错”，即在搜索过程中不断地做出选择，如果选择正确，则继续向前搜 索；否则，回退到上一个状态，重新做出选择。回溯算法通常⽤于解决具有多个解，且每个解都需要 搜索才能找到的问题。
2. 回溯算法的模板
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 表⽰当前可以做的选择。在回溯算法中，我们需 要做出选择，然后递归地调⽤回溯函数。如果满⾜结束条件，则将当前路径添加到结果集中；否则， 我们需要撤销选择，回到上⼀个状态，然后继续搜索其他的选择。 回溯算法的时间复杂度通常较高，因为它需要遍历所有可能的解。但是，回溯算法的空间复杂度较低，因为它只需要维护⼀个状态树。在实际应用中，回溯算法通常需要通过剪枝等方法进⾏优化，以减少搜索的次数，从⽽提高算法的效率。
3. 回溯算法的应用
- 组合问题
- 排列问题
- 子集问题
总结
回溯算法是⼀种⾮常重要的算法，可以解决许多组合问题、排列问题和搜索问题等。回溯算法的核心思想是搜索状态树，通过遍历状态树来实现对所有可能解的搜索。回溯算法的模板非常简单，但是实现起来需要注意⼀些细节，比如如何做出选择、如何撤销选择等。
4. 全排列
首先我们看到这个题目，立马就会想到使用穷举来解决，依次选取一个位置来枚举，但是假如我们这个题目给的数组是100个，那么岂不要写100个for循环来枚举，太麻烦了，我们使用dfs来解决，使用dfs之前我们首先要画出我们的决策树，我们以实例一为例。
此时就要用到我们的递归方法，当我们使用递归的时候，我们仅需关心某一个节点在干什么事情，只要我们当前的节点没有使用过，我们就可以添加进去，同时还要注意几个细节问题，
那我们就可以直接来写代码了。
class Solution {
vector<int> path;
vector<vector<int>> ret;
bool check[7] = {false}; // 标记下标是否已经使用
public:
vector<vector<int>> permute(vector<int>& nums) {
dfs(nums);
return ret;
}
void dfs(vector<int>& nums)
{
if(path.size() == nums.size())
{
ret.push_back(path);
return;
}
for(int i = 0; i < nums.size(); i++)
{
if(check[i] == false)
{
path.push_back(nums[i]);
check[i] = true;
dfs(nums);
// 回溯 -> 恢复现场
path.pop_back();
check[i] = false;
}
}
}
};5. 子集
经过之前的全排列我们可以知道，要想解决一个递归的题目，我们就必须要画好我们的决策树，决策树画的越详细，题目越容易做出来，这个题目有两种决策树，我们分别画出来分别写一下代码。第一个决策树是根据元素选与不选来抉择的。
此时我们设计dfs函数的时候，有两个参数dfs(nums, i)，nums就表示数组，而i就是表示是否选择这个下标对应的值，当我们选择的时候，就可以直接将nums[i]添加到path中，然后递归到dfs(nums, i+1)下一层，如果不选，就直接递归dfs(nums, i+1)下一层，当我们到叶子节点的时候，就可以返回啦！
class Solution {
vector<vector<int>> ret;
vector<int> path;
public:
vector<vector<int>> subsets(vector<int>& nums) {
dfs(nums, 0);
return ret;
}
void dfs(vector<int>& nums, int pos)
{
if(pos == nums.size())
{
ret.push_back(path);
return;
}
// 选
path.push_back(nums[pos]);
dfs(nums, pos + 1);
path.pop_back(); // 恢复现场
// 不选
dfs(nums, pos + 1);
}
};我们在来画出另外一种决策树，依据每层元素的个数来画，每次选完当前元素时，就从后面元素继续选择。
根据上面的决策树，每一层的节点都是枚举后面的数，所以我们的函数设计时dfs(nums, pos)，pos当前层枚举的数，此时我们就要来一个for循环解决，同时我们还能发现此时我们不需要bool数组来检查元素是否被使用过，因为我们通过pos控制每一层的节点都是枚举后面的数，不会美剧到已经使用过的值，那什么时候统计结果呢？在进入for循环之前就可以直接统计结果啦。
class Solution {
vector<vector<int>> ret;
vector<int> path;
public:
vector<vector<int>> subsets(vector<int>& nums) {
dfs(nums, 0);
return ret;
}
void dfs(vector<int>& nums, int pos)
{
ret.push_back(path);
for(int i = pos; i < nums.size(); i++)
{
path.push_back(nums[i]);
dfs(nums, i + 1);
path.pop_back(); // 恢复现场
}
}
};6. 找出所有子集的异或总和再求和
这个题目其实就是子集题目的变种题目，我们依然是使用的dfs来求出子集，只不过此时我们不需要再创建数组存储每个子集，只需要使用一个变量path存储子集的异或结果和一个变量ret存储所有子集的疑惑和结果即可。
class Solution {
int ret = 0;
int path = 0;
public:
int subsetXORSum(vector<int>& nums) {
dfs(nums, 0);
return ret;
}
void dfs(vector<int>& nums, int pos)
{
ret += path;
for(int i = pos; i < nums.size(); i++)
{
path ^= nums[i];
dfs(nums, i + 1);
path ^= nums[i]; // 恢复现场
}
}
};7. 全排列 Ⅱ
首先我们这个题目是全排列的一个变种题目，这个题目中要求全排列之后不能出现重复的值，因此我们可以按照上面求全排列的方法求出结果，然后再利用set容器进行去重来解决这个题目，但是比较繁琐，我们可以利用剪枝来求解，我们先画出我们的决策树。
此时我们就可以有两种判断方法，只关心合法的分支，合法我们才去dfs，合法的肯定是当前位置并没有被使用，所以check[i] == false，同时我们还要满足，nums[i]不能和nums[i-1]位置的元素相等，但是我们可以看到左边的分支，如果check[i-1]的位置是已经被使用了，那么虽然nums[i]和nums[i-1]位置的元素相等，我们仍然可以使用这个元素，因为这两个元素不在同一层，最后还有一个条件，如果i==0，那么此时我们肯定是合法的，此时可以直接添加。
此时我们就可以来直接写代码啦！
class Solution {
vector<vector<int>> ret;
vector<int> path;
bool check[8] = { false };
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(), nums.end()); // 先排序
dfs(nums);
return ret;
}
void dfs(vector<int>& nums)
{
if(path.size() == nums.size())
{
ret.push_back(path);
}
for(int i = 0; i < nums.size(); i++)
{
// 剪枝
if((i == 0 || nums[i-1] != nums[i] || check[i - 1] == true) && check[i] == false)
{
path.push_back(nums[i]);
check[i] = true;
dfs(nums);
// 恢复现场
path.pop_back();
check[i] = false;
}
}
}
};8. 电话号码的字母组合
看到这个题目，我们首先想到的就是for循环去解决问题，但是如果传入的digits特别多，那么就要使用很多的for循环，因此这个题目我们也可以使用dfs来解决，首先我们要做的就是画出我们的决策树。
首先我们就需要根据电话进行数字与字母的映射，我们这里直接创建一个数组即可，随后的工作就和全排列的思路差不多，直接上手代码。
class Solution {
string hash[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
string path;
vector<string> ret;
public:
vector<string> letterCombinations(string digits) {
if(digits.empty())
return ret;
dfs(digits, 0);
return ret;
}
void dfs(string& digits, int pos)
{
if(pos == digits.size())
{
ret.push_back(path);
return;
}
string tmp = hash[digits[pos] - '0'];
for(int i = 0; i < tmp.size(); i++)
{
path += tmp[i];
dfs(digits, pos + 1);
path.pop_back(); // 恢复现场
}
}
};9. 括号生成
对于这样的问题，我们首先要了解的就是什么是有效的括号组合呢？第一就是左括号的数量等于右括号的数量，其次是从头开始的任意一个字串，左括号的数量大于右括号的数量。接下来我们就要做的就是画出决策树，决策树画的越详细，题目越容易做出来。
随后我们就可以直接来手写代码啦！！！
class Solution {
vector<string> ret;
string path;
int left = 0;
int right = 0;
int n1 = 0;
public:
vector<string> generateParenthesis(int n) {
n1 = n;
dfs();
return ret;
}
void dfs()
{
if(n1 == right)
{
ret.push_back(path);
return;
}
// 选左括号
// 左括号的数量小于n
if(left < n1)
{
path += '(';
left++;
dfs();
path.pop_back(); // 恢复现场
left--;
}
// 选右括号
// 右括号的数量小于左括号的数量
if(left > right)
{
path += ')';
right++;
dfs();
path.pop_back(); // 恢复现场
right--;
}
}
};10. 组合
这个题目其实就是上面的子集的变种题目，我们依然是先来画出我们的决策树。
随后我们就直接来写代码啦。
class Solution {
vector<vector<int>> ret;
vector<int> path;
int n1, k1;
public:
vector<vector<int>> combine(int n, int k) {
n1 = n;
k1 = k;
dfs(0);
return ret;
}
void dfs(int pos)
{
if(k1 == path.size())
{
ret.push_back(path);
return;
}
for(int i = pos; i < n1; i++)
{
path.push_back(i + 1);
dfs(i + 1);
path.pop_back(); // 恢复现场
}
}
};
