首页 > 编程语言 >LeetCode算法训练-回溯总结

LeetCode算法训练-回溯总结

时间:2023-02-28 21:24:37浏览次数:43  
标签:递归 个数 LeetCode 算法 树层 回溯 节点

欢迎关注个人公众号:爱喝可可牛奶

LeetCode算法训练-回溯总结

适用问题

  • 组合问题:N个数里面按一定规则找出k个数的集合
  • 排列问题:N个数按一定规则全排列,有几种排列方式
  • 切割问题:一个字符串按一定规则有几种切割方式
  • 子集问题:一个N个数的集合里有多少符合条件的子集
  • 棋盘问题:N皇后,解数独等等

通用模板

result 存放结果集
path 某个符合条件的结果
void backtracking(参数) {
    if (终止条件) {
        result.add(path);
        return;
    }
    
    for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
        处理节点;
        backtracking(路径,选择列表); // 递归
        回溯,撤销处理结果
    }
}

个人理解

  1. 回溯和递归紧密相联,有递归就有回溯

  2. 回溯的过程可以抽象为一个回溯树,要搞清楚题目要求的是分支节点、叶子节点、还是所有节点

  3. 去重 回溯树的同一个树枝去重(用全局used数组) 同一个树层上去重(for循环外的局部used数组)

  4. 画回溯树找条件写代码,什么时候要添加结果,什么时候要continue,要不要以及能不能对原始数据集排序

  5. 剪枝优化 什么情况下不用再递归树枝不用递归树层,这时可直接在for循环中给出限制条件

  6. 回溯函数遍历树枝,for循环++遍历树层

标签:递归,个数,LeetCode,算法,树层,回溯,节点
From: https://www.cnblogs.com/cupxu/p/17166034.html

相关文章

  • 算法基础1.2.2浮点数二分
    前言直接先把整数二分看完看整数二分文章点这里现在只需要补充几个特点(其实整数二分的博客的前言就介绍了一些)就可以了由于浮点数二分没有向下取整的特性(不懂的话就去......
  • 2月28日——算法微入门
    以上课程内容均来自于武汉大学李春葆教授的网课,为李教授第一周所讲内容。(接下来括号里面全部都是吐槽,不看也罢)(可惜我不小心把我的AI删掉了(网速不行也下不回来),不然我可以......
  • 基本算法之二分查找法折半查找(Java)
    前提条件:数组中的数据必须是有序的!核心思想:每次排除一半的数据,查询数据的性能明显提高很多!      publicclassTask{publicstaticvoidmain(Stri......
  • 算法基础1.2.1整数二分
    前言如果第一次接触二分其实很难理解它的含义我对二分的理解就是找到一个条件,能够保证所有数据对于这个条件要么是True要么是False。二分的作用是查找。二分本质不是单......
  • 【并查集】LeetCode 990. 等式方程的可满足性
    题目链接990.等式方程的可满足性思路并查集模板题,模板可以参考常用算法模板。将字母视为结点,==表示有路径,!=表示无路径。遍历x==y,建立图前驱关系遍历x!=y,......
  • 程序设计竞赛算法与实现考点总结(模板)
    一,转换(星期计算)栗:给定一个日期,问这个日期是星期几?Mothod1---根据这个日期与今天的距离X,假设今天是星期Y,给定日期是今天星期之前:((Y-X)%7+7)%7+1;......
  • 7 回溯算法理论基础
    回溯法:也可以叫做回溯搜索法,它是一种搜索的方式。在二叉树系列中,已经不止一次,提到了回溯,回溯是递归的副产品,只要有递归就会有回溯。回溯法的效率:回溯的本质是穷举,穷举所有......
  • 【LeetCode二叉树#11】最大二叉树(构造二叉树)
    最大二叉树力扣题目地址(opensnewwindow)给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下:二叉树的根是数组中的最大元素。左子树是通过数组......
  • 高并发场景下常见的限流算法及方案介绍
    作者:京东科技康志兴应用场景现代互联网很多业务场景,比如秒杀、下单、查询商品详情,最大特点就是高并发,而往往我们的系统不能承受这么大的流量,继而产生了很多的应对措施:CD......
  • #yyds干货盘点# LeetCode程序员面试金典:珠玑妙算
    题目:珠玑妙算游戏(thegameofmastermind)的玩法如下。计算机有4个槽,每个槽放一个球,颜色可能是红色(R)、黄色(Y)、绿色(G)或蓝色(B)。例如,计算机可能有RGGB4种(槽1为红色,槽2、3为绿......