本文并不基于示例说明算法，而是在接下来的博文中介绍回溯法的具体运用。
这里首先详细说明回溯算法的原理和思路。
在了解回溯算法之前，首先说明回溯算法中涉及到的知识点的概念。 便于理解博文。哈哈，大家可能都不罗嗦，直接想知道什么是回溯法，但是基础不好，后面的运用怎么才能彻底掌握呢？ 不要麻烦，要有耐心。 这个其实很容易理解。 嗳气！
1.1问题的解空间
因为一个复杂问题的解决方案是由几个小决策步骤组成的决策序列，所以一个问题的解可以表示为解向量x=(x1，x2， xn )。 其中，分量xi对应于第I步的选择，x中分量xi的所有可能值的组合构成问题的解向量空间。 被简称为解空间或解空间树，因为一个解向量往往对应于有问题的状态，所以解空间也被称为问题的3358www.Sina.com/
状态空间树。解空间中满足约束条件的解空间；
可行解：:在解空间中使目标函数最大或最小的可行解
这里，取球数组a的幂集合，对解空间树进行说明；
解：解向量x=(x1，x2，x3 )，Xi=1)1=I=3)意味着选择ai，Xi=0意味着不选择ai。 求解过程分为三个步骤，每个步骤对a的三个要素进行确定(选择或未选择)。 对应的解空间图如上图所示，每个叶的节点构成一个解。 例如，I节点的解向量为(1，1，0 )，对应解为(1，-2)。
求解一个问题的过程是搜索相应的解空间寻找满足目标函数的解，因此是算法设计的关键；
)1) :节点如何扩展？ 例如，在求幂集合的问题中，第I层节点的扩展方法有选择ai或不选择ai 2种。
)2) :解空间树种如何搜索？ 一个是DFS，回溯法就是这样。 另一个是BFS，分支极限法是这样的；
)3) :解空间树通常很庞大，如何有效地寻找问题的解；
有两种类型的求解空间树。
最优解:给定的问题是从n个要素的集合s中发现满足某一性质的子集时，对应的解空间树。 如上图所示
子集树:给定的问题是在确定n个元素满足某一性质的序列时，对应的解空间树。
应该注意的是，问题的解空间树是虚拟的，算法运行时不需要构建真正的树结构。
那么，太罗嗦了，我来说明算法。
1.2何谓回溯法：
根据DFS算法的策略，从节点中搜索解空间树。 首先，子节点变为排列树，同时变为当前的活结点。 指产生子节点的节点，也称为e节点
在当前扩展节点中，搜索在深度方向上移动到新节点。 这个新节点成为新的活节点，成为现在的扩展节点。 如果当前扩展节点不能在深度方向上移动，则当前扩展节点为扩展结点。 此时，请将死结点还原到最近的活节点，使该活节点成为当前的扩展节点。 回溯法就是这样递归地搜索解空间，直到找到所要求的解为止，或者直到解空间中没有活节点为止。
所以追溯法体现了离家出走不通就返回的想法。
回溯
1 .回溯求解时，有返回祖先节点的过程，需要保存搜索到的节点。 通常有两种。 一种是子定义并保存堆栈。 二：采用递归方法。
2 .回溯法中，通常采用两种策略避免无效探索。 (一)在这里注意：扩展节点中切割不满足约束条件的路径； )用约束函数切割无法得到问题解或最佳解的路径。 将这两种函数统称为限界函数
在此，总结用回溯法求解的一般步骤。
)针对给定问题确定问题的解空间树
)2)确定节点的扩展搜索规则。
)3)用深度优先方式搜索解空间树，在搜索中可以采用剪枝函数避免无效搜索。 在此，深度优先方式可以采用递归回溯或非递归(重复性)回溯。
好了，回溯到此为止。 如果有不明白的地方请问我。 嗯嗯。 另外，我在说些什么。
剪枝函数
两者的区别如下。
)1)访问顺序不同：深度优先遍历的目的是“遍历”，因为本质是无序的，关键是是否被访问，所以在实现中，针对每个站点是否被访问就足够了。 回溯法的目的是“求解过程”，本质必须是有序的，也就是说所有步骤都必须按照要求的顺序。
)2)访问次数的不同)深度优先遍历不再访问已经访问的顶点。 在回溯法中，已经访问过的顶点有可能再次访问。
(3)剪枝差异：深度优先遍历不包括剪枝。
实际上，除了剪枝是回溯法的明显特征之一外(任何回溯法都不包括剪枝部分)，很难严格区分回溯法和深度优先遍历。 由于这些算法大多是递归算法，递归调用中隐含着状态的自动回滚和恢复。