回溯
回溯是一种穷举，但与brute force有一些区别，回溯带了两点脑子的，并不多，brute force一点也没带。
-
- 回溯知道回头；相反如果是brute force，发现走不通立刻跳下山摔死，换第二条命从头换一条路走。
-
- 回溯知道剪枝；如果有一条岔路上放了一坨屎，那这条路我们不走，就可以少走很多不必要走的路。
DFS
DFS是一种开路策略，就是一条道先走到头，再往回走一步换一条路走到头，这也是回溯用到的策略。在树和图上回溯时人们叫它DFS。
递归
递归是一种行为，回溯和递归如出一辙，都是一言不合就回到来时的路，所以一般回溯用递归实现；当然也可以不用，用栈。
回溯的解题思路
所谓回溯都是这样的思路：在当前局面下，你有若干种选择。那么尝试每一种选择。如果已经发现某种选择肯定不行（因为违反了某些限定条件），就返回；如果某种选择试到最后发现是正确解，就将其加入解集。
所以你思考递归题时，只要明确三点就行：选择 (Options)，限制 (Restraints)，结束条件 (Termination)。即“ORT原则”（这个是我自己编的）
关于回溯的三种问题
有没有解
返回值是true/false。
程序模版：
boolean solve(Node n) {
if n is a leaf node {
if the leaf is a goal node, return true
else return false
} else {
for each child c of n {
if solve(c) succeeds, return true
}
return false
}
}
求所有解
求个数，设全局counter，返回值是void；求所有解信息，设result，返回值void。
程序模版：
void solve(Node n) {
if n is a leaf node {
if the leaf is a goal node, count++, return;
else return
} else {
for each child c of n {
solve(c)
}
}
}
求最优解
设个全局变量best，返回值是void。
程序模版：
void solve(Node n) {
if n is a leaf node {
if the leaf is a goal node, update best result, return;
else return
} else {
for each child c of n {
solve(c)
}
}
}