C++数据结构--回溯算法

一.什么是回溯算法算法思想:在包含问题的所有解的解空间树中,按照深度优先搜索的策略,从根节点出发深度搜索解空间树。当搜索到某一节点时,要先判断该节点是否包含问题的解;如果包含就从该节点出发继续深度搜索下去,否则逐层向上回溯。一般在搜索的过程中都会添加相应的剪枝函数,避免无效解的搜索,提高算法效率。解空间:解空间就是所有解的可能取值构成的空间,一个解往往包含了得到这个解的每一步,往往就是对应解空间树中一条从根节点到叶子节点的路径。子集树和排列树都是一种解空间,它们不是真实存在的数据结构,也就是说并不是真的有这样一颗树,只是抽象出的解空间树。二.基于子集树回溯算法子集树是算法设计中特别是在使用回溯法解决问题时一种非常典型的解空间结构。简单来说当一个问题需要从 n 个元素的集合 S 中找出满足某种特定性质的子集时所有可能解构成的树形结构就称为子集树即子集树常解决子集问题。子集树的核心思想是对于集合中的每一个元素都只有两种选择要1 或 不要0。遍历子集树的算法时间复杂度通常为 O(2^n)。例如我们要找一个数组{123}的所有子集。三.基于排列树的回溯算法简单来说当一个问题需要确定 n 个元素满足某种性质的排列即顺序时所有可能的排列构成的树形结构就称为排列树即排列树常解决排列顺序问题。排列树的核心思想是在每一步决策中从剩余未选择的元素中挑选一个放到当前位置。遍历排列树的算法时间复杂度通常为 O(n!)。例如我们找一个数组{123}的全部排列形式