也叫回溯搜索法，它是一种搜索的方式
- 本质：是【穷举】，所以效率很低，如果想让回溯法高效一些，可以加一些剪枝的操作
- 解决的问题：需要迭代 for 循环 n 次的暴力搜索非常不好写，只能用回溯法去搜索
- 理解：可以抽象为【树形结构】，因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度构成树的深度，递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）
模板：
function backtracking(参数) {
if (终止条件) {
存放结果
return
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点
backtracking(路径，选择列表) // 递归
回溯，撤销处理结果
}
}其中 for 循环横向遍历，递归纵向遍历
组合问题
重点：需要一个 tmp 保存临时的路径，最终递归结束时将结果放入 res 中，同时需要一个额外变量记住下次开始遍历的起始数字 index 剪枝：也可以进行剪枝，通过剩下元素个数是否还满足要求，即判断 i 能够遍历的范围进行剪枝
leetcode：
- 77. 组合 - 力扣（LeetCode） （经典问题）
- 39. 组合总和 - 力扣（LeetCode） (数字可以重复，所以 i 不用加 1 再传入下层递归)
- 40. 组合总和 II - 力扣（LeetCode） (有重复元素，先排序，同一层遍历中有相邻相同元素则去掉)
- 216. 组合总和 III - 力扣（LeetCode） (加了不同的终止条件)
- 377. 组合总和 Ⅳ - 力扣（LeetCode） (记忆化)
排列问题
leetcode：
子集问题
leetcode：
分隔问题
leetcode：
其他问题
leetcode：
总结
都需要一个 tmp 数组保存中间回溯状态
遍历范围
组合问题：
如果始终在一个集合里进行回溯，需要传入一个 index 进行递增遍历：
- 可以重复选取：index 不用加 1
- 不能重复选取：index 需要加 1
如果每次循环的集合都不同：则 index 用来选择不同的遍历集合
排列问题：
每次都在相同范围内选择，不用传 index
去重
树层去重有 2 种：
- 可以排序：排序后比较相邻元素：
if (i > index && nums[i] === nums[i - 1]) - 不能排序：每层定义一个 Set 记录该层已遍历元素（在回溯函数内部进行定义）：
if (usedSet.has(nums[i])) continue
树枝去重：
- 使用一个全局的 Set 集合进行记录即可（在回溯函数外部进行定义）
取结果
分为 2 种：
- 遍历到叶子节点时取结果
- 遍历过程中就可以取结果