侧边栏壁纸
博主头像
thinkTV博主等级

喜爱动漫的二刺螈一枚,摩托车云爱好者(快要有车了)。 懂一点技术的在读生物医学工程研究生( •̀ ω •́ )✧,多多指教。

  • 累计撰写 127 篇文章
  • 累计创建 17 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

代码随想录算法训练营第三十天 | 回溯法总结

thinkTV
2023-05-18 / 0 评论 / 0 点赞 / 107 阅读 / 748 字 / 正在检测是否收录...

代码随想录:原文

1. 回溯法理论基础

  • 回溯是递归的副产品,只要有递归就会有回溯
  • 回溯法就是暴力搜索
  • 回溯算法能解决如下问题:
    1. 组合问题:N个数里面按一定规则找出k个数的集合
    2. 排列问题:N个数按一定规则全排列,有几种排列方式
    3. 切割问题:一个字符串按一定规则有几种切割方式
    4. 子集问题:一个N个数的集合里有多少符合条件的子集
    5. 棋盘问题:N皇后,解数独等等

回溯三部曲

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
        处理节点;
        backtracking(路径,选择列表); // 递归
        回溯,撤销处理结果
    }
}

2. 组合问题

  • 用递归控制for循环嵌套的数量
  • for循环横向遍历,递归纵向遍历,回溯不断调整结果集

图片1

2.1 组合总和

  • 求组合总和回溯算法求组合问题加了一个元素总和的限制
  • 已选元素总和如果已经大于n(题中要求的和)了,那么往后遍历就没有意义了,直接剪掉

图片2

2.2 组合总和(二)

  • 本题没有数量要求,可以无限重复,但是有总和的限制,所以间接的也是有个数的限制
  • 如果是一个集合来求组合的话,就需要startIndex
  • 如果是多个集合取组合,各个集合之间相互不影响,那么就不用startIndex

2.3 组合总和(三)

  • 集合元素会有重复,但要求解集不能包含重复的组合
  • 理解“树枝去重”和“树层去重”
  • 可以看出在candidates[i] == candidates[i - 1]相同的情况下:
    1. used[i - 1] == true,说明同一树枝candidates[i - 1]使用过
    2. used[i - 1] == false,说明同一树层candidates[i - 1]使用过

图片2

2.4 多个集合求组合

  • 因为本题每一个数字代表的是不同集合,也就是求不同集合之间的组合

2.5 切割问题

  • 切割问题用求解组合问题的思路来解决
  • 需要startIndex模拟切割线

图片3

3. 子集问题

  • 在树形结构中子集问题是要收集所有节点的结果,而组合问题是收集叶子节点的结果
result.push_back(path); // 收集子集,要放在终止添加的上面,否则会漏掉结果
if (startIndex >= nums.size()) { // 终止条件可以不加
    return;
}

4. 排列问题

排列问题的特点:

  • 每层都是从0开始搜索而不是startIndex
  • 需要used数组记录path里都放了哪些元素了
    即树层去重,效率更高
0

评论区