回溯法就是一种有组织的系统化搜索技术，可以看作是蛮力法穷举搜索的改进。
回溯法每次只构造可能解的一部分，然后评估这个部分解，如果这个部分解有可能导致一个完整解，则对其进一步构造，否则，就不必继续构造这个部分解了。回溯法常常可以避免搜索所有的可能解，所以，它适用于求解组合数量较大的问题。
1.概述1.1问题的解空间复杂问题常常有很多的可能解，这些可能解构成了问题的解空间。解空间也就是进行穷举的搜索空间，所以，解空间中应该包括所有的可能解。
为了用回溯法求解一个具有n个输入的问题，一般情况下，将其可能解表示为满足某个约束条件的等长向量X=(x1,x2,……,xn)，其中分量xi(1<=i<=n)的取值范围是某个有限几何Si={ai1,ai2,……,airi}，所有可能的解向量构成了问题的解空间。
问题的解空间一般用解空间树的方式组织，因为解空间树能将解空间形象化。如0/1背包问题，
蛮力法是对整个解空间树中的所有可能解进行穷举搜索的一种方法，但是，只有满足约束条件的解才是可行解，只有满足目标函数的解才是最优解，这就有可能减少搜索空间。回溯法从根节点出发，按照深度优先策略遍历解空间树，搜索满足约束条件的解。在搜索至树中任一结点时，先判断该结点对应的部分解是否满足约束条件，或者是否超出目标函数的界，也就是判断该节点是否包含问题的（最优）解，如果肯定不包含，则跳过对以该结点为根的子树的搜索，即所谓的剪枝；否则，进入以该结点为根的子树，继续按照深度优先策略搜索。
回溯法的搜索过程涉及的结点只是整个解空间树的一部分，在搜索过程中，通常采用两种策略避免无效搜索：(1)用约束条件减去得不到可行解的子树;（2）用目标函数剪去得不到最优解的子树。这两类函数统称为剪枝函数。
1.3回溯法的求解过程
图着色问题描述为：给定无向连通图G=(V,E)和正整数m，求最小的整数m，使得用m种颜色对G中的顶点着色，使得任意两个相邻顶点着色不同。
首先把所有顶点的颜色初始化为0，然后依次为每个顶点着色。在图着色问题的解空间树中，如果从根节点到当前节点对应一个部分解，也就是所有的颜色指派都没有冲突，则在当前节点处选择第一棵子树继续搜索，也就是为下一个顶点着颜色1，否则，对当前子树的兄弟子树继续搜索，也就是为当前顶点着色下一个颜色，如果所有m种颜色都已尝试过并且发生冲突，则回溯到当前节点的父结点处，上一个顶点的颜色被改变，以此类推。
对于下图中求解三着色问题，在解空间树中，从根节点出发，搜索第一棵子树，即为顶点A着颜色1，再搜索节点2的第一棵子树，即为顶点B着颜色1，这导致一个不可行解，回溯到节点2，选择节点2的第二棵子树，即为顶点B着颜色2，在为顶点C着色时，经过着颜色1和2的失败尝试后，选择节点4的第三棵子树，即为顶点C着颜色3，在节点7选择第一颗子树，就为顶点D着颜色1，但是在为顶点E着色时，顶点E无论着3种颜色的哪一种均发生冲突，于是导致回溯，在节点7选择第二棵子树也会发生冲突，于是，选择节点7的第三棵子树，即顶点D着颜色3，在节点10选择第一棵子树，即为顶点E着颜色1，得到了一个解(1,2,3,3,1)。注意到，解空间树中共有243个节点，而回溯法只搜索了其中的14个节点后就找到了问题的解。
- 416. 分割等和子集https://leetcode-cn.com/problems/partition-equal-subset-sum/ - 中等 代码https://github.com/shidawuhen/asap/blob/master/controller/algorithm/partitionequalsubsetsum.go
要求从一个城市出发，经过每个城市恰好一次，然后回到出发城市。
下图(a)所示是一个无向图，在解空间树中从根结点1开始搜索。首先将x1值为1，到达结点2，表示哈密顿回路从顶点1开始。然后将x2置为1，到达结点3，但顶点1重复访问，搜索节点3的兄弟子树，将x2置为2，构成哈密顿回路的部分解(1,2)，在经过节点5和节点6的失败尝试后，将x3置为3，将哈密顿回路的部分解扩展到(1,2,3)，在经过节点8、节点9和节点10的失败尝试后，将x4置为4，将哈密顿回路的部分解扩展到(1,2,3,4)，在经过节点12、节点13、节点14和节点15的失败的尝试后，将x5置为5，将哈密顿回路的部分解扩展到(1,2,3,4,5)，但是在图(a)中从顶点5到顶点1没有边，引起回溯；将x4置为5，到达节点17，构成哈密顿回路的部分解(1,2,3,5)，在经过节点18、19和20的失败的尝试后，将x5置为4，将哈密顿回路的部分解扩展到(1,2,3,5,4)，而在图(a)中从顶点4到顶点1存在边，所以，找到了一条哈密顿回路(1,2,3,5,4,1)，搜索过程结束。注意到，解空间树中共有243个节点，而回溯法只搜索了其中的21个节点后就找到了问题的解。在解空间树中的搜索构成如图(b)所示。
