引言
寻找问题的解的一种可靠的方法是首先列出所有候选解，然后依次检查每一个，在检查完所有或部分候选解后，即可找到所需要的解。理论上，当候选解数量有限并且通过检查所有或部分候选解能够得到所需解时，上述方法是可行的。
不过，在实际应用中，很少使用这种方法，因为候选解的数量通常都非常大（比如指数级，甚至是大数阶乘），即便采用最快的计算机也只能解决规模很小的问题。
对候选解进行系统检查的方法有多种，其中回溯和分枝定界法是比较常用的两种方法。按照这两种方法对候选解进行系统检查通常会使问题的求解时间大大减少（无论对于最坏情形还是对于一般情形）。事实上，这些方法可以使我们避免对很大的候选解集合进行检查，同时能够保证算法运行结束时可以找到所需要的解。因此，这些方法通常能够用来求解规模很大的问题。
概念
回溯算法也叫试探法，它是一种系统地搜索问题的解的方法（一种选优搜索法，按选优条件向前搜索，以达到目标）。当搜索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术称为：回溯法，而满足回溯条件的某个状态的点称为：“回溯点”。
回溯法实际是穷举算法，按问题某种变化趋势穷举下去，如某状态的变化用完还没有得到最优解，则返回上一种状态继续穷举。
许多复杂的，规模较大的问题都可以使用回溯法，回溯算法有“通用解题方法”的美称，其采用了一种“走不通就掉头”思想作为其控制结构，用它可以求出问题的所有解和任意解。
它的应用很广泛，很多算法都用到回溯法，例如，迷宫，八皇后问题，图的m着色总是等都用到回溯法，当然其中还使用了其他策略。
基本思想
回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。
确定了解空间树的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间树。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。
如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。
回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。
步骤
用回溯算法解决问题的一般步骤为：
- 定义一个解空间树，它包含问题的解。解空间：至少包含问题的一个解。
- 利用适于搜索的方法组织解空间树。
- 利用深度优先法搜索解空间树。
- 利用限界函数避免移动到不可能产生解的子空间树。
问题的解空间树通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。
