回溯算法理论基础
回溯算法题目分类：
回溯概念
回溯法也可以叫做回溯搜索法，它是一种搜索的方式。
在二叉树系列中，我们经常提到了回溯，回溯是递归的副产品，只要有递归就会有回溯。所以以下内容中，回溯函数也就是递归函数，指的都是一个函数。
回溯法并不是什么高效的算法：
因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。
那么既然回溯法并不高效为什么还要用它呢？
因为没得选（题目太难），一些问题能暴力搜出来就不错了，撑死了再剪枝一下，还没有更高效的解法。
回溯法解决的问题
回溯法，一般可以解决如下几种问题：
- 组合问题：N个数里面按一定规则找出k个数的集合
- 切割问题：一个字符串按一定规则有几种切割方式
- 子集问题：一个N个数的集合里有多少符合条件的子集
- 排列问题：N个数按一定规则全排列，有几种排列方式
- 棋盘问题：N皇后，解数独等等
其中：组合是不强调元素顺序的，排列是强调元素顺序。
例如：{1, 2} 和 {2, 1} 在组合上，就是一个集合，因为不强调顺序，而要是排列的话，{1, 2} 和 {2, 1} 就是两个集合了。
记住组合无序，排列有序，就可以了。
如何理解回溯法
回溯法解决的问题都可以抽象为树形结构！
因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度就构成了树的深度。
递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。
77.组合
思路
组合中的回溯本质上就是n重for循环的嵌套
例如：范围为1-100，k为50的情况下，问题转变为->数组有一个1+范围2-100，k为49，以此基础作为递归的逻辑,即有该问题有100个分支，每个分支都要不断递归后续数字求解。
将组合问题抽象为如下树形结构：
最后是终止条件，在写for循环中已经有了终止条件，就是不断向数组path中添加节点，一直到添加到n(100)结束；但本题所需节点个数要是k个，所以，还要写一个终止条件（也可以说是收集条件）if(k == 0)进行处理，处理完成后返回即可，不许要继续向下遍历，因为超过k个就已经无效了。
回溯的精华在于path.pop_back()的理解，弹出时path也要回复原状态！
题解
class Solution {
public:
vector<int> path;
vector<vector<int>> res;
void backtracking(int start, int end ,int k)
{
if(k == 0)
{
res.push_back(path);
return ;
}
for(int i = start;i<=end;i++)
{
path.push_back(i);
backtracking(i+1,end,k-1);
path.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
backtracking(1,n,k);
return res;
}
};
216.组合总和III
题目链接：216.组合总和III
文档讲解：代码随想录
状态：学习组合后，轻松AC
思路
与77.组合类似，只不过由k个数转变为了(加和为n)&&(k个数)
题解
class Solution {
public:
vector<int> path;
vector<vector<int>> res;
void backtracking(int k, int n,int start)
{
if(k == 0)//是终止条件，我觉得更像是收集者
{
if(n == 0)res.push_back(path);
return ;
}
for(int i = start;i<=9;i++)
{
path.push_back(i);
backtracking(k-1, n-i,i+1);
path.pop_back();//实际是递归子树的过程
}
}
vector<vector<int>> combinationSum3(int k, int n) {
backtracking(k,n,1);
return res;
}
};
17.电话号码的字母组合
题目链接：17.电话号码的字母组合
文档讲解：代码随想录
状态：理清传递参数，so easyのAC
思路
首先要获得输入的数字与字母的映射，使用字典vector<string> dic{"","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}
传入回溯函数时，回溯函数自己调用自己，所以要把用到的小字符串全部传入，如"abc"、"def"等，需要建立一个vector<string>数组参数。
接下来就是传统的组合问题了，注意收割条件即可！
题解
class Solution {
public:
vector<string> res;
string s;
vector<string> dic{"","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
vector<string> chart;
void backtracking(vector<string> chart,int start)
{
if(chart.size() == 0)return;
if(s.size() == chart.size())
{
res.push_back(s);
return;
}
for(int i = 0;i<chart[start].size();i++)
{
s += chart[start][i];
backtracking(chart,start+1);
//if(start+1<=chart.size())其实在收割时已经保证了不会越界
s.pop_back();
}
}
vector<string> letterCombinations(string digits) {
for(auto i:digits)chart.push_back(dic[i-'1']);
backtracking(chart,0);
return res;
}
};