回溯算法
概论
回溯法（Backtracking）的思想： 能进则进，不进则换，不换则退。
回溯法也可以叫做回溯搜索法，它是一种搜索的方式。
回溯是递归的副产品，只要有递归就会有回溯。
因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。
回溯法解决的问题都可以抽象为树形结构，因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度就构成了树的深度。
递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。
回溯算法的框架：
以DFS的方式进行搜索，在搜索的过程中用剪枝条件（限界函数）避免无效搜索。约束函数，在扩展结点处剪去得不到可行解的子树；限界函数：在扩展结点处剪去得不到最优解的子树。
回溯算法求解问题的一般步骤：
1、 针对所给问题，定义问题的解空间，它至少包含问题的一个（最优）解。
2 、确定易于搜索的解空间结构,使得能用回溯法方便地搜索整个解空间 。
3 、以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。
常用剪枝函数：
用约束函数在扩展结点处剪去不满足约束的子树；
用限界函数剪去得不到最优解的子树。
回溯法，一般可以解决如下几种问题：
- 组合问题：N个数里面按一定规则找出k个数的集合
- 切割问题：一个字符串按一定规则有几种切割方式
- 子集问题：一个N个数的集合里有多少符合条件的子集
- 排列问题：N个数按一定规则全排列，有几种排列方式
- 棋盘问题：N皇后，解数独等等
回溯算法的设计
回溯算法模板
回溯算法模板框架如下：
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}
Although backtracking seems very efficient. The time complexity for this algorithm is O(n2^n).
2^n is the time for searching the solution space.
n is the time to store the best solution.
解空间树
子集树、满m叉树、排列树区别：
子集树：从n个元素的集合S中找到满足某种性质的子集时，相应的解空间树就成为了子集树（典型问题：01背包问题）
满m叉树：所给问题中每一个元素均有m中选择，要求确定其中的一种选择，使得对这n个元素的选择结果组成的向量满足某种性质（经典问题：图的m着色问题）
排列树：从n个元素的排列树中找出满足某种性质的一个排列的时候，相应的解空间树称为排列树（经典问题：TSP问题，n-queens 问题）
剪枝（Pruning）操作
在回溯过程中，我们用一个约束函数C(i)（constraint function）和一个限界函数B(i)（bounding function）剪掉无效的分支，从而专注于搜索最有希望的分支。
类似dfs在叶子节点收获结果，回溯算法可以通过剪枝（prune）提前中止向下搜索的过程。
约束函数C(i)（constraint function）：检查当前解的可行性
Constraint function is to check the feasibility of the current solution.
限界函数B(i)（bounding function）
Bounding function is for optimization problem.
回溯法的典型应用
集装箱问题（Container Loading Problem）
Container Loading problem is to load as many containers as is possible without sinking the ship.
子集和（Sum of Subsets）
0/1 Knapsack Problem
First, rank the item by their value per unit weight.