回溯算法

回溯的处理思想，有点类似 枚举搜索。我们枚举所有的解，找到满足期望的解。为了有规律地枚举所有可能的解，避免遗漏和重复，我们把问题求解的过程分为 多个阶段。每个阶段，我们都会面对一个岔路口，我们先随意选一条路走，当发现这条路走不通的时候（不符合期望的解），就回退到上一个岔路口，另选一种走法继续走。

回溯算法特征总结：

回溯算法就是一种暴力穷举算法
穷举的过程就是遍历一棵多叉树的过程
回溯算法的代码框架和多叉树遍历的代码框架类似

通常解决问题：

组合问题：N 个数里面按一定规则找出 k 个数的集合
切割问题：一个字符串按一定规则有几种切割方式
子集问题：一个 N 个数的集合里有多少符合条件的子集
排列问题（强调顺序）：N 个数按一定规则全排列，有几种排列方式
棋盘问题：N 皇后、解数独等等

回溯法解决的问题都可以抽象为树形结构，是的，我指的是所有回溯法的问题都可以抽象为树形结构！因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度。递归就要有终止条件，所以必然是一颗高度有限的树（N 叉树）。

算法思想

在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。

若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。

算法特征

回溯算法的特征：

深度优先遍历（DFS）：回溯算法一般采用 DFS 求解，因此满足递归的一般特征
子集：回溯题目一般都要求求解所有的最优解，因此，DFS 的终止条件就是判断是否得到了一个最优解，然后直接返回
遍历空间集：在每一轮 DFS 中都需要遍历空间集，根据题目性质，有的需要从 0 开始，有的需要从当前位置开始
剪枝：在遍历空间集的时候，需要优先将不符合条件的去除掉，不然会做很多无用的递归调用，导致超时
加入元素：遍历空间集的时候，加入每一个元素，然后再 DFS
移除元素：当一轮 DFS 达到终止条件结束的时候，说明当前选择已经完成，需要返回到上一轮做其他选择，因此需要将上一轮选择时加入的元素删除掉

设计思路

全局变量：保存结果
参数设计：递归函数的参数，是将上一次操作的合法状态当作下一次操作的初始位置。这里的参数，可以理解为两种参数：状态变量和条件变量
1. 状态变量就是最后结果要保存的值
2. 条件变量就是决定搜索是否完毕或者合法的值
完成条件：完成条件时决定状态变量和条件变量在取什么值时可以判定整个搜索流程结束，搜索流程结束有两种含义：搜索成功并保存结果和搜索失败并返回上一次状态
递归过程：传递当前状态给下一次递归进行搜索

const fn = function () {
  // 定义全局变量保存最终结果
  let ans = [];
  // 定义状态变量保存当前状态
  let arr = [];
  // 定义条件变量（一般条件变量就是题目直接给的参数）
  let p,q,r

  const backtracking = (state, condition1, condition2, ...) => {
    // 不满足合法条件（可以说是剪枝）
    if (/* 终止条件 */) return;

    // 状态满足最终要求
    if () {
      ans.push()
    }

    // 满足执行条件
    backtracking(...)
  };

  backTracking();

  return ans;
};

剪枝策略

剪枝策略就是在搜索过程中利用 过滤条件 来剪去完全不用考虑（已经判断这条路走下去得不到最优解）的搜索路径，从而 避免了一些不必要的搜索，大大优化了算法求解速度，还保证了结果的正确性。

应用到回溯算法中，我们就可以 提前判断当前路径是否能产生结果集，如果否，就可以提前回溯。而这也叫做 可行性剪枝。

另外还有一种叫做 最优性剪枝，每次记录当前得到的 最优值，如果当前结点已经无法产生比当前最优解更优的解时，可以提前回溯，eg：分支限界算法。

通过经典题目的训练，目前常用在回溯法求解问题的技巧主要有四种，解题时依据问题性质通过混用其中一至多种可实现机械化解题。

名称	说明	例子
`used` 备忘录（`i = 0`）	避免重复相同的选择（排列）	`[2,2,3]` 或 `[2,3,2]` 视为不同列表
`startIndex` 索引（`i = startIndex`）	避免重复相同的选择 + 避免顺序不同，但组合相同的解（组合/子集/切割）	`[2,2,3]` 和 `[2,3,2]` 视为相同列表
`sort` 相邻去重 `!(input[i-1] === input[i])`	输入有重复时，避免重复完全相同的解	避免 `[2,2,3]` 和 `[2,2,3]` 共现
`set` 非相邻去重 `!set.count(input[i])`	输入有重复 + 不能排序时，避免重复完全相同的解
`backtracking(args){}`	只返回一个解使用 `if(backtracking()) return true`

⚠️ 注意：

相邻去重需要先通过 arr.sort() 转化为递增有序数组

经典题目：

系列问题	题目	使用的剪枝策略
排列问题	46. 全排列	备忘录+
	47. 全排列 II
子集问题	78. 子集	索引
	90. 子集 II	备忘录+索引+相邻去重
组合总和	39. 组合总和	索引
	40. 组合总和 II	备忘录+索引+相邻去重

Data Structure and Algorithms Guidebook

回溯算法

算法思想

算法特征

设计思路

剪枝策略

相关题目

参考资料