回溯理论基础

回溯和递归是相辅相成的，只要有递归就有回溯（执行完一次递归就自动回溯到上一层）

回溯的效率

回溯不是一个高效的算法，而是一个纯暴力的过程

<aside> 💡

有些问题没有更好的解法，只能使用暴力搜索，这时就可以使用回溯法。包括以下问题

  1. 组合问题
  2. 切割问题
  3. 子集问题
  4. 排列问题
  5. 棋盘问题（N皇后、解数独等） </aside>

如何理解回溯法

回溯法解决的问题都可以抽象为树形结构（N叉树）

image.png

回溯法的模板

void backtracking( 参数 ){
    // 终止条件
    if( 终止条件 ){
          收集结果（通常在叶子节点收集结果）
          return;
    }

    // 单层逻辑（通常为一个for循环，每次循环都继续递归）
    for(集合元素集){
           // 处理节点的操作（判断当前节点的合法性）
           // 递归
           // 回溯（还原，撤销对节点的操作）
					 // （去重操作）
    }
}

<aside> 💡

回溯三部曲：

  1. 确定递归函数的参数与返回值：返回值一般是void
  2. 确定递归的终止条件
  3. 确定单层递归的逻辑 </aside>

题目