回溯算法是什么？
回溯法(搜索和回溯法)是选拔搜索法，也叫启发式法，根据选拔条件进行前进搜索，实现目标。 但是，在探索了某一步的时候，如果原来的选择不优秀或者没有达到目标，就返回一步重新选择。 这样，如果不顺利就返回的技术是回溯法，将满足有回溯条件的状态的点称为“回溯点”。
可以解决什么问题？
数组、组合(子集、幂集、字符的全部数组)。 传递值时，对于数组问题，删除一个使用过的元素； 问题是删除前面的所有要素。 给定数组、字符串、特定的规则，搜索迭代试图找到某个解。 二维数组中的DFS搜索(八皇后，黄金矿工，数独)如何理解回溯算法？
为问题建立空间结构
在求解空间结构的基础上进行DFS检索
追溯出口和剪枝点减少无效搜索，在出口保存有效解
如何理解回溯的解空间
回溯算法有两种常见的解空间模型，分别对应数学中的两种暴力思想、组合及排列。 其中的子集问题对应数学中的组合问题。 序列问题对应数学中的序列问题。
然后基于这两个leetcode主题，分析了应该如何构造回溯解空间，其他主题几乎都是基于这两个基础主题变形而来的。
全排列问题分析
案例：排序数组[ 1，2，3 ]的解空间如下，树结构整体可以用以下逻辑来理解。
节点表示当前状态，路径表示当前选择
每个节点代表求解“全阵列”问题的不同阶段，这些阶段由变量的“不同值”表示，这些值可称为状态或路径
必须使用DFS遍历整个搜索树，并在搜索节点返回上一层时重置状态
遍历叶节点将退出。 判断方法是根据现在的深度判断候补要素是否消失
组合问题分析
组合问题的解空间构成
节点表示状态，按现在选择了哪个要素的每个分支，表示要素选择的方式扩展节点时，可以进行如下适当的剪枝
回溯算法的设计思路
全局变量:结果参数设计：保存候选列表。 用于解析空间扩展节点的扩展路径。 用于记录当前节点的列表选择状态条件变量。 结束回溯的判定条件和修剪分枝的判定条件全局变量。 用于存储各过程的解回溯实现:回溯的代码可以主要分为三个部分来制作回溯出口。 找到满足限制条件的解，记录该解并返回。 通常放在函数的入口节点会变宽。 从候选列表中选择适当的元素进行递归求解。 节点扩展阶段需要改变路径和条件变量以适应新节点。 扩展的规则主要有两种数组情况：数组和组合。 必须每次都选择未选择的元素组合。 每次只能向后选择，不能向前选择，从后向前选择时会出现重复问题选择子串。 在这种情况下，与数组和组合不同，两者都是一次选择一个元素。 现在，在这种情况下选择连续的数组，属于组合情况下的特别列。 修剪树枝。 修剪树枝的操作是为了减去解空间中不合适的树枝。 可以在回溯出口处检测到剪枝，也可以在节点扩展时检测到剪枝。算法模板
result=[]//记录最终结果的func backtrack (选择列表、路径、条件变量) ://回溯剪枝//回溯出口指定的解if为结束条件： result.add (通过检查要选择的元素是否符合主题规定的规则(//check ) )选择///更改路径和条件变量值backtrack )的路径)取消选择//路径和条件变量值选择列表是指当前层为DDD参考文献
回溯算法模板
回溯法的解空间表示方法
通过全序列问题理解回溯算法
递归与回溯的区别
《剑指offer》 2.4.3节
回溯法例题
leetcode数组组合编程问题