回溯算法介绍

回溯算法的理解

1. 回溯问题最重要的就是根据题意画出树形结构图，然后分析 for 循环为树的宽度、递归为树的深度

2. 回溯的本质是暴力求解（暴力枚举）

3. 回溯通过剪枝操作可以进行优化

回溯模板代码

function backtrack() {
  let res = []; // 最终结果集
  let path = []; // 当前路径

  function _backtrack(参数) {
    if (终止条件) {
      存放结果;
      return;
    }
    for (选择： 本层集合中元素（ 树中节点孩子的数量就是集合的大小）) {
      处理节点; // 做选择
      _backtrack(参数); // 递归
      回溯， 撤销处理结果 // 撤销选择
    }
  }

  _backtrack(参数)
  return res;
}

画图分析

1. 问题1：集合中存在重复元素或不存在重复元素

2. 问题2：每层 for 循环从哪里开始遍历

3. 问题3：每进行一次操作是否应作为结果进行收集

4. 问题4：在同一集合中操作还不同集合中操作