一、什么是回溯算法
回溯算法是一种经典的递归算法，通常用于解决组合问题、排列问题和搜索问题等。
回溯算法的基本思想:从一个初始状态开始，按照一定的规则向前搜索，当搜索到某个状态无法前进时，回退到前一个状态，再按照其他的规则搜索。回溯算法在搜索过程中维护一个状态树，通过遍历状态树来实现对所有可能解的搜索。
回溯算法的核心思想：“试错”，即在搜索过程中不断地做出选择，如果选择正确，则继续向前搜索;否则，回退到上一个状态，重新做出选择。回溯算法通常用于解决具有多个解，且每个解都需要搜索才能找到的问题。
1.回溯算法的模板：
void backtrack(vector<int>& path,vector<int>& choice,...)
{
//满足结束条件
if(/*满足结束条件*/)
{
res.push_back(path);
return;
}
//遍历所有选择
for(int i=0;i<choice.size();i++)
{
//做出选择
path.push_back(choice[i]);
//做出当前选择后继续搜索
backtrack(path,choice);
//撤销选择(剪枝)
path.pop_back();
}
}其中，path 表示当前已经做出的选择，choice表示当前可以做的选择。在回溯算法中，我们要做出选择，然后递归地调用回溯函数。如果满足结束条件，则将当前路径添加到结果集中；否则，我们需要撤销选择，回到上一个状态，然后继续搜索其他的选择。回溯算法的时间复杂度通常较高，因为它需要遍历所有可能的解。但是，回溯算法的空间复杂度较低，因为它只需要维护一个状态树。在实际应用中，回溯算法通常需要通过剪枝等方法进行优化，以减少搜索的次数，从而提高算法的效率。
我们不应该太依赖于模板，因为模板可能会限制我们的思维。我们会下意识的想去套用模板，而每道题目的解题方式都是不太一样的，需要我们理解回溯算法，根据题目去做出调整。
2.回溯的思考方式
1.画出决策树，越详细越好。
2.设计代码
全局变量：...
dfs函数：仅需关心某一个结点在干什么事情。
细节问题：回溯、剪枝、递归出口。
3.回溯算法的应用
组合问题
组合问题是指从给定的一组数(不重复)中选取出所有可能的k个数的组合。例如，给定数集[1,2,3]，要求选取 k=2 个数的所有组合。
结果为:
1 [1,2]
2 [1,3]
3 [2,3]
排列问题
排列问题是指从给定的一组数(不重复)中选取出所有可能的k个数的排列。例如，给定数集[1,2,3]，要求选取 k=2 个数的所有排列。
结果为:
1 [1,2]
2 [2,1]
3 [1,3]
4 [3,1]
5 [2,3]
6 [3,2]
子集问题
子集问题是指从给定的一组数中选取出所有可能的子集，其中每个子集中的元素可以按照任意顺序排列。例如，给定数集[1,2.3]，要求选取所有可能的子集。
结果为:
1
2 [1]
3 [2]
4 [3]
5 [1,2]
6 [1,3]
7 [2,3]
8 [1,2,3]
总结
回溯算法是一种非常重要的算法，可以解决许多组合问题、排列问题和搜索问题等。回溯算法的核心思想是搜索状态树，通过遍历状态树来实现对所有可能解的搜索。回溯算法的模板非常简单，但是实现起来需要注意一些细节，比如如何做出选择、如何撤销选择等。
二、示例题目
1.全排列. - 力扣（LeetCode）
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1] 输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1] 输出：[[1]]
解法:
算法思路:
典型的回溯题目，我们需要在每一个位置上考虑所有的可能情况并且不能出现重复。通过深度优先搜索的方式，不断地枚举每个数在当前位置的可能性，并回溯到上一个状态，直到枚举完所有可能性，得到正确的结果。
每个数是否可以放入当前位置，只需要判断这个数在之前是否出现即可。具体地，在这道题目中，我们可以通过一个递归函数 bfs 和标记数组 check 来实现全排列。
画出决策树
设计代码：
全局变量：vector<vector<int>> ret;存放结果
vector<int> path;记录路径
bool check[];记录元素是否被使用
细节：回溯：干掉path最后一个元素、修改check数组。
递归出口：遇到叶子结点的时候，直接添加结果。
class Solution {
vector<vector<int>> ret;
vector<int> path;//记录路径
bool check[7];//记录元素是否被使用
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;
}
}
}
};2.子集. - 力扣（LeetCode）
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的
子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0] 输出：[[],[0]]
解法一:
算法思路:
为了获得 nums数组的所有子集，我们需要对数组中的每个元素进行选择或不选择的操作，即 nums数组一定存在 2^(数组长度) 个子集。对于查找子集，具体可以定义一个数组，来记录当前的状态，并对其进行递归。
对于每个元素有两种选择:1.不进行任何操作;2.将其添加至当前状态的集合。在递归时我们需要保证递归结束时当前的状态与进行递归操作前的状态不变，而当我们在选择进行步骤2进行递归时，当前状态会发生变化，因此我们需要在递归结束时撤回添加操作，即进行回溯。
递归流程如下:
1.递归结束条件:如果当前需要处理的元素下标越界，则记录当前状态并直接返回；
2.在递归过程中，对于每个元素，我们有两种选择:
- 不选择当前元素，直接递归到下一个元素;
- 选择当前元素，将其添加到数组末尾后递归到下一个元素，然后在递归结束时撤回添加操作;
3.所有符合条件的状态都被记录下来，返回即可。
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);
}
};解法二：
当子集中有0个、1个、2个、3个......元素时。从每个数的后面去选。每个结点都是一个结果。
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();
}
}
};