回溯法 backtrack

递归回溯

对解空间进行深搜，一般情况下，可用递归来实现。

递归回溯框架：

void Backtrack(int t){
   if ( t > n ) Output(x);
   else{
         for (int i = f(n,i); i<= g(n,i) ;i++){
              x[t] = h(i);
              if ( Constraint(t) && Bound(t) ) Backtrack(t+1);   
         }
   }   
}        

其中，参数t 代表当前的递归深度。

t > n ，即算法已经搜索到叶子节点。即递归的递归出口。输出可行解x。

f(n,i) g(n,i) 分别代表在当前的递归深度下，未搜索子树的起始编号和结束编号。

h(i)  代表可选值。

此时，如果满足 约束函数 和 边界条件 ，可以进入下一层。

如果不满足，就进行了剪枝操作。

执行完 for 循环，已经搜索遍当前这一层。返回 t-1 层继续执行。

当   t=1时，若已经测试完所有  x[1] 的 可选值，外层调用就全部结束。

调用一次 Backtrack(1)即可完成整个回溯搜索的过程。

例题  leetcode 22