回溯算法核心思想：试错和回退
- 构建一个搜索树（或递归树），在搜索树上进行深度优先遍历
- 发现当前路径不可能得到有效解决方案时，会进行剪枝操作（即回退到上一步），继续搜索其他路径
回溯算法实践问题
回溯算法实现思路
- 核心在于找到：递归式和递归边界
- 递归式：树形逻辑模型的构建，关键在于找 “坑位”，一个坑位就对应树中的一层，每一层的处理逻辑往往是一样的
- 递归边界：要么在题目中约束得非常清楚，要么默认为“坑位” 数量的边界
回溯算法伪代码
function xxx(入参) {
前期的变量定义、缓存等准备工作
const path = []
dfs(起点)
dfs(递归参数) {
if(到达了递归边界) {
结合题意处理边界逻辑，往往和 path 内容有关
return
}
for(遍历坑位的可选值) {
path.push(当前选中值)
处理坑位本身的相关逻辑
path.pop()
}
}
}