回溯算法

1. 回溯算法概述

回溯算法（backtracking algorithm）是一种通过穷举来解决问题的方法，它的核心思想是从一个初始状态出发，暴力搜索所有可能的解决方案，当遇到正确的解则将其记录，当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，直到找到解或者尝试了所有可能的选择都无法找到解为止。这种走不通就退回再走的技术称为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

回溯算法通常采用深度优先搜索来遍历解空间，前序、中序和后序遍历都属于深度优先搜索。回溯算法的核心思想有两点：

1. 深度优先搜索：回溯算法基于深度优先搜索的思想，它会沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点所在的路径无法得到有效的解时，算法会回溯到上一个节点，尝试其他的路径继续搜索。
2. 穷举与剪枝：本质上是对所有可能的解进行穷举搜索，但与纯粹的暴力枚举不同，回溯算法会在搜索过程中根据问题的约束条件进行剪枝操作，避免对一些明显不可能产生解的分支进行搜索，从而提高搜索效率。