1 定义
回溯是递归的一种形式，同时也是递归的副产品，也就是说只要有递归就会有回溯。在遇到必须从多种选项中选择一项的时候，你选择了一项后又会出现多种选项供选择，直到选择到了“正确的选项”函数才结束。因此，回溯法解决的问题都可以抽象为树形结构（不一定是二叉树）。
回溯虽然是一种非常典型的递归算法，但是任何递归算法都可以重写为堆栈算法。事实上，这就是递归算法被翻译成机器或汇编语言的方式。
2 算法思想
回溯法就是暴力搜索，并不是什么高效的算法，最多再剪枝一下（dfs的优化）。因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度。因为用到了递归，是递归就必须要有终止条件（basecase），在树状结构中，这棵树（N叉树）的高度必须是有限制。
在此，我引入“原问题”和“子问题”这两个概念来帮助大家理解回溯。题目要求解决的问题，可以看成是一个原问题。而在这整个原问题中，其中的一个选项就可以看作是一个子问题，如此循环往复：该子问题本身，又可以看成是一个新的原问题。
3 代码模板
3.1 递归实现
void trackback(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
trackback(路径，选择列表); // 递归
pop//回溯，撤销处理结果
}
}
在这其中，这个for循环本身是一个横向遍历，也就是说一个根节点的下一层有多少个子节点，这个循环就会执行多少次；for循环中的trackback函数调用就是一个递归的过程，是一个纵向遍历，也就是说这棵树有多少层，这个函数就会递归多少次。pop的这个操作就是回溯。
3.2 栈实现
bool solve(Node& n) {
创建一个栈stack;
将节点n压入stack；
while（!stack.empty()） {
if 栈顶部是叶子节点 {
if（该节点是目标节点） return true；
else stack.pop();
}
else {
if 栈顶部的节点有未尝试的子节点
将下一个未尝试的子节点推到栈上;
else 把它从栈顶弹出;
}
return false;
}
4 例题
4.1 例题1
【leetcode-17】给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
4.1.1 题目分析
首先使用哈希表存储每个数字对应的所有可能的字母，然后进行回溯操作。
回溯过程中维护一个字符串，表示已有的字母排列（如果未遍历完电话号码的所有数字，则已有的字母排列是不完整的）。该字符串初始为空。每次取电话号码的一位数字，从哈希表中获得该数字对应的所有可能的字母，并将其中的一个字母插入到已有的字母排列后面，然后继续处理电话号码的后一位数字，直到处理完电话号码中的所有数字，即得到一个完整的字母排列。然后进行回退操作，遍历其余的字母排列。
回溯算法用于寻找所有的可行解，如果发现一个解不可行，则会舍弃不可行的解。在这道题中，由于每个数字对应的每个字母都可能进入字母组合，因此不存在不可行的解，直接穷举所有的解即可。
4.1.2 代码实现
class Solution {
public:
vector letterCombinations(string digits) {
vector combinations;
if(digits.empty()){
return combinations;
}
unordered_map phoneMap{
{'2', "abc"},
{'3', "def"},
{'4', "ghi"},
{'5', "jkl"},
{'6', "mno"},
{'7', "pqrs"},
{'8', "tuv"},
{'9', "wxyz"}
};
string combination;
traceback(combinations,combination,0,phoneMap,digits);
return combinations;
}
void traceback(vector& combinations,string& combination,int i,unordered_map& phoneMap,string& digits){
if(i == digits.size()){
combinations.push_back(combination);
return;
}else{
char digit = digits[i];
auto letters = phoneMap[digit];
for(auto letter:letters){
combination.push_back(letter);
traceback(combinations,combination,i+1,phoneMap,digits);
combination.pop_back();
}
}
}
}; 4.2 例题2
【leetcode-144】给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
4.2.1 题目分析
这道题可以用递归暴力获取答案，但是，这里给出一种用栈实现的更为巧妙的解法，其结构与bfs中的基本模板有些类似。只不过，在栈中，数据履行“先进后出”的原则，使用在将子节点压入栈是，要先压右节点，后压左节点。
4.2.2 代码实现
class Solution {
public:
vector preorderTraversal(TreeNode* root) {
vector ans;
if(!root){
return ans;
}
stack s;
s.push(root);
while(!s.empty()){
auto node = s.top();
s.pop();
ans.push_back(node->val);
if(node->right){
s.push(node->right);
}
if(node->left){
s.push(node->left);
}
}
return ans;
}
};