回溯算法实际上是一个类似枚举的搜索尝试过程，主要在搜索尝试过程中寻找问题的解，当发现已经不满足求解条件时，就回溯返回，尝试别的路径。
回溯法是一种选优搜索法，按选优条件向前搜索，以达到目的。当搜索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择。这种走不通就回退再重新走的机制叫做回溯法，满足回溯条件的某个状态被称为“回溯点”。
回溯本质上是一种穷举，是一种类型的递归。什么情况下用回溯法比较好？
- 判断回溯很简单，拿到一个问题，你感觉如果不穷举一下就没法知道答案，那就可以开始回溯了。
一般回溯的问题有三种：
- Find a path to success 有没有解
- Find all paths to success 求所有解
- 求所有解的个数
- 求所有解的具体信息
- Find the best path to success 求最优解
某种问题的解我们很难去找规律计算出来，没有公式可循，只能列出所有可能的解，然后一个个检查每个解是否符合我们要找的条件，也就是通常说的遍历。而解空间很多是树型的，就是树的遍历。
其次，树的先序遍历，也就是根是先被检查的，二叉树的先序遍历是根，左子树，右子树的顺序被输出。如果把树看做一种特殊的图的话，DFS就是先序遍历。所以，回溯和DFS是联系非常紧密的，可以认为回溯是DFS的一种应用场景。另外，DFS有个好处，它只存储深度，不存储广度。所以空间复杂度较小，而时间复杂度较大。
最后，某些解空间是非常大的，可以认为是一个非常庞大的树，此时完全遍历的时间复杂度是难以忍受的。此时可以在遍历的同时检查一些条件，当遍历某分支的时候，若发现条件不满足，则退回到根节点进入下一个分支的遍历。这就是“回溯”这个词的来源。而根据条件有选择的遍历，叫做剪枝或分枝定界。
基本思想
在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。
若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。
而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。
回溯法解决问题的步骤
- 针对所给问题，确定问题的解空间：
- 首先应明确定义问题的解空间，问题的解空间应至少包含问题的一个 (最优) 解。
-
确定结点的扩展搜索规则
- 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
算法框架
（1）问题框架
设问题的解是一个 $n$ 维向量 $(a_1,a_2,\dots,a_n)$，约束条件是 $a_i(i=1,2,3,\dots,n)$ 之间满足某种条件，记为 $f(a_i)$。
（2）非递归回溯框架
int a[n],i;
初始化数组a[];
i = 1;
while (i>0(有路可走) and (未达到目标)) // 还未回溯到头
{
if(i > n) // 搜索到叶结点
{
搜索到一个解，输出；
}
else // 处理第i个元素
{
a[i]第一个可能的值；
while(a[i]在不满足约束条件且在搜索空间内)
{
a[i]下一个可能的值；
}
if(a[i]在搜索空间内)
{
标识占用的资源；
i = i+1; // 扩展下一个结点
}
else
{
清理所占的状态空间； // 回溯
i = i –1;
}
}
（3）递归的算法框架
回溯法是对解空间的深度优先搜索，在一般情况下使用递归函数来实现回溯法比较简单，其中 $i$ 为搜索的深度，框架如下：
int a[n];
try(int i)
{
if(i>n)
输出结果;
else
{
for(j = 下界; j <= 上界; j=j+1) // 枚举i所有可能的路径
{
if(fun(j)) // 满足限界函数和约束条件
{
a[i] = j;
... // 其他操作
try(i+1);
回溯前的清理工作（如a[i]置空值等）;
}
}
}
}
模板：
void dfs(int 当前状态)
{
if(当前状态为边界状态)
{
# 记录或输出
return;
}
for(i=0;i<n;i++) # 横向遍历解答树所有子节点
{
# 扩展出一个子状态。
# 修改了全局变量
if(子状态满足约束条件)
{
dfs(子状态)
}
# 恢复全局变量//回溯部分
}
}
应用回溯法有：
- 装载问题
- 批处理作业调度
- 符号三角形问题
- n后问题
- 0-1背包问题
- 最大团问题
- 图的m着色问题
- 旅行售货员问题
- 圆排列问题
- 电路板排列问题
- 连续邮资问题
LeetCode 题目：