Tag X. BackTracking

1. General Algorithm

Pick a starting point.

while(Problem is not solved)

For each path from the starting point.

check if selected path is safe, if yes select it

and make recursive call to rest of the problem

If recursive calls returns true, then return true.

else undo the current move and return false.

End For

If none of the move works out, return false, NO SOLUTON.

2. 中文简介：

1） 本质就是深度优先搜索。回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

2） 回溯法是一个通用的算法，能够找到一些计算问题的所有解， 通常是一些满足约束问题。 通过遍历的方法寻找解，不断深入搜索，如果确定这部分不可能有解，则放弃这部份的搜索， 继续下一部分的搜索

3） 适用：当需要找出它的解集（全部解）或者要求回答什么解是满足某些约束条件的最优解时，往往要使用回溯法。

4） 时间复杂度分析： 一般都是O(2^n)