回溯法

回溯法是一种选优搜索法又称为试探法

按选优条件向前搜索以达到目标但当探索到某一步时发现原先选择并不优或达不到目标就退回一步,重新选择这种走不通就退回再走的技术为回溯法

而满足回溯条件的某个状态的点称为回溯点

回溯法三个关键点

1. 路径：也就是已经做出的选择。

2. 选择列表：也就是你当前可以做的选择。

3. 结束条件：也就是到达决策树底层，无法再做选择的条件。

回溯法算法框架

result = [];
function backtrack(路径, 选择列表) {
  if (满足结束条件) {
    result.add(路径);
    return;
  }
  for (let i = 0; i < 选择列表的长度; i++) {
    做选择;
    backtrack(路径, 选择列表);
    撤销选择;
  }
}

解决问题

回溯算法能进行暴力的搜索，它解决的问题是需要暴力才能解决的问题, 以下列举回溯能解决的六种常见问题类型。

1. 组合问题

比如请给出数字[1, 2, 3, 4]两两组合的每种可能性，结果就是[12, 13, 14, 23, 24, 34]，因为 23 和 32 是一个组合，所以忽略 32。如果你说这个很简答了，使用循环也可以解决，那题目条件换一下，给出数字 1 - 20 之间每 12 种组合的可能性，这时遍历就不好使了。

2. 排列问题

给出[1, 2, 3]所有的全排列的可能性，结果就是[123, 132, 213, 231, 312, 321]。

3. 子集问题

给出数字[1, 2, 3]所有的子集(幂集)的可能性，结果就是[[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]。

4. 分割问题

给出一个数字字符串 25525511135，返回它所有组成 IP 地址格式的可能，结果就是["255.255.11.135", "255.255.111.35"]。

5. floodFill 填色问题

问题类型参考力扣 200 岛屿和 547 朋友圈，之后详细介绍。

6. 棋盘问题

类型参考解数独和 8 皇后问题，之后详细介绍。

上述的六种类型看着区别可能挺大，其实它们都是树型问题这个类型，这个到具体问题讲解时再说明其中的道道。