回溯算法介绍
lkj 4/8/2022 回溯
# 回溯算法的理解
回溯问题最重要的就是根据题意画出树形结构图,然后分析 for 循环为树的宽度、递归为树的深度
回溯的本质是暴力求解(暴力枚举)
回溯通过剪枝操作可以进行优化
# 回溯模板代码
function backtrack() {
let res = []; // 最终结果集
let path = []; // 当前路径
function _backtrack(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择: 本层集合中元素( 树中节点孩子的数量就是集合的大小)) {
处理节点; // 做选择
_backtrack(参数); // 递归
回溯, 撤销处理结果 // 撤销选择
}
}
_backtrack(参数)
return res;
}
# 画图分析
问题1:集合中存在重复元素或不存在重复元素
问题2:每层 for 循环从哪里开始遍历
问题3:每进行一次操作是否应作为结果进行收集
问题4:在同一集合中操作还不同集合中操作