回溯算法

定义：回溯算法，又称“试探法”。解决问题时， 每一步都是尝试态度，如果发现并不是好的，

或者这么走下去很定达不到目标，立刻返回重新操作， 这种走不通就回退的方法为回溯算法。

回溯 vs 递归

很多人认为 回溯 和 递归 是一样的， 其实不然。回归中可以看到递归的影子

但是两者是有区别的。

回溯： 从问题本身出发，寻找可能实现的所有可能情况。和

穷举法的思想相近，不同于穷举法是将所有的情况列举出来以后在一一筛选，而回溯法是在列举

过程中，如果发现当前情况不对，就停止后续工作，返回上一步，进行新的尝试。

递归： 是从问题的结果出发，例如求n！的结果，就需要知道

n(n-1)! 的结果，而要想知道 (n-1)! 结果，就需要提前知道 (n-1)(n-2)!。这样不断地向

自己提问，不断地调用自己的思想就是递归。

两者联系： 回溯可以用递归思想实现

实现过程：

使用回溯法解决问题的过程，实际上是建立一棵“状态树”的过程。例如，在解决列举集合{1,2,3}

所有子集的问题中，对于每个元素，都有两种状态，取还是舍，所以构建的状态树为：

回溯算法的求解过程实质上是先序遍历“状态树”的过程。树中每一个叶子结点，都有可能是问题的

答案。图 1 中的状态树是满二叉树，得到的叶子结点全部都是问题的解。

在某些情况下，回溯算法解决问题的过程中创建的状态树并不都是满二叉树，因为在试探的过程中，

有时会发现此种情况下，再往下进行没有意义，所以会放弃这条死路，回溯到上一步。在树中的体现，

就是在树的最后一层不是满的，即不是满二叉树，需要自己判断哪些叶子结点代表的是正确的结果。