回溯法概述_晓梦林的博客-程序员宅基地

技术标签: # leetcode刷题笔记  

别看回溯法很难,但回溯法就是暴力解法

回溯法是什么?

回溯法是一种搜索的方式,也叫做回溯搜索法。

在二叉树 leetcode 259 中,我就用到了回溯。

回溯和递归,就是被包含和包含的关系。只要有递归,就会有回溯。
所以,回溯函数也是递归函数。

回溯法性能评估

其性能不高,因为回溯的本质是穷举,穷举所有可能,然后选出我们想要的答案。再进一步优化,就是剪枝操作。
有些难题就需要“回溯搜索+剪枝”来解决。

回溯法解决的实际问题

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

对回溯法的理解

可以把回溯法抽象为树形结构,它主要解决的就是在集合中递归查找子集,集合的大小构成了树的快递,递归的深度,构成了树的深度。

我们都知道,递归是有终止条件的,所以该树的深度也是有限的。

回溯法套路

①确定回溯函数参数以及返回值
一般是看程序逻辑,再确定需要相应的参数。
返回值一般为void型。

伪代码如下:

void backtracking(参数) 

②确定终止条件
按照树的思路去理解,找到叶子节点,记录结果,结束本层递归。
伪代码如下:

if (终止条件) {
    
    存放结果;
    return;
}

③确定搜索的遍历逻辑
回溯法一般在集合中递归搜索,集合大小构成了树的宽度,递归的深度构成树的深度。

如下图所示:
在这里插入图片描述
上图中,集合的大小和孩子的数量是相等的。

回溯函数遍历过程伪代码如下:

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

for循环就是遍历集合区间,一个节点有多少个孩子,这个for循环就执行多少次。

backtracking,自己调用自己,实现递归。

上图中,for循环是横向遍历,backtracking(递归)就是纵向遍历,这样一棵树全遍历完了,所以,搜索叶子节点,就是找到其中一个结果。

回溯算法模板框架如下:

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

    for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
    
        处理节点;
        backtracking(路径,选择列表); // 递归
        回溯,撤销处理结果
    }
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_25953411/article/details/117517280

智能推荐

java url url_基于java URL和URLConnection(详解)_创业青年骁哥的博客-程序员宅基地

URL类将URL地址封装成对象,提供了解析URL地址的方法,如获取uri部分、host部分、端口等。URLConnection则是URL对象和Socket连接给结合起来了,使得可以更轻松地获取发起URL请求的连接套接字。1.URLimport java.net.MalformedURLException;import java.net.URL;public class URLDemo {publi...

【IDEA】Theme & Settings_Mr.tai的博客-程序员宅基地

一、下载主题网址 http://color-themes.com/?view=index我选择 Ladies Night 2二、导入主题file –> import setttings –> 选中主题jar文件 –> 一路确认 –> 重启三、设置主题file –> settings –> editor –> color scheme –>...

Dapper安装教程_weixin_44620938的博客-程序员宅基地

1、使用可视化界面安装a、选择要安装的项目或解决方案,右键选项选择管理NuGet包b、在搜索框内搜索"Dapper",选择安装即可c、安装进度如下图2、使用程序包管理器控制台安装在程序包管理器控制台输入以下命令:Install-Package Dapper -Version 1.50.2...

在阿里云Serverless K8S集群上部署Spark任务并连接OSS(详细步骤)_Sicilly_琬姗的博客-程序员宅基地_阿里云spark

在阿里云ASK集群上部署Spark任务并连接OSS简介ASK是阿里云的一个产品,属于Serverless Kubernetes 集群,这次实验是要在ASK集群上运行Spark计算任务(以WordCount为例),另外为了能让计算和存储分离,我使用了阿里云OSS来存放数据。(连接OSS这块找了好多资料都不全,在本地可以运行的代码一放在集群就报错,遇到很多bug才终于弄好了,记录下来希望对以后的小伙伴有帮助)环境准备本机需要安装:JAVA jdk1.8IDEAMavenDocker(安装在Li

Python代码在运行出现时语法错误:IndentationError: unindent does not match any outer indentation level_waitstory12的博客-程序员宅基地

问题:Python代码在运行出现时语法错误:IndentationError: unindent does not match any outer indentation level解决方法:Python代码中混用了TAB键和空格键,所以出现上述错误的提示。我使用的Python版本是Python3.5.1。我使用的文本编辑器是Notepad++,可以设置显示所有的字符的。在: 视图 -> 显...

dw的php选择滑动图片效果,页面图片浮动左右滑动效果的简单实现案例_神秘还作业的博客-程序员宅基地

核心代码:1.css:16sucai.csshtml,body {height: 100%;margin: 0px;padding: 0px;}a {outline: none;}img{ border:0;}a img {vertical-align: top;}a img.last {margin-right: 0; }.box {width: 850px;height: auto;overf...

随便推点

(GO_GTD_2)基于OpenCV和QT,建立Android图像处理程序_jsxyhelu2015的博客-程序员宅基地

一、综述 如何采集图片?在windows环境下,我们可以使用dshow,在linux下,也有ffmpeg等基础类库,再不济,opencv自带的videocapture也是提供了基础的支撑。那么在andoird下,使用的肯定是Android自带的相关函数了。由于Android是基于java语言的,如果我们想要调用Android的相关函数,那么必须通过JNI的方法。 ...

Vue:基本用法。_weixin_30636089的博客-程序员宅基地

一、起步1.下载核心库vue.jsbower info vue #查看版本号npm init --yes #下载vue.jscnpm install vue --save版本 v2.5.17 目前最新版本()vue2.0比1.0相比最大的变化就是引入Virtual DOM(虚拟DOM),页面更新效率高,速度更快2.hello world(对比 angular)2.1angu...

BM25和Lucene Default Similarity比较 (原文标题:BM25 vs Lucene Default Similarity)_weixin_30852367的博客-程序员宅基地

原文链接: https://www.elastic.co/blog/found-bm-vs-lucene-default-similarity原文 By Konrad Beiske翻译 By 高家宝这篇文章是之前讨论相似度模型(vsm和bm25)的文章的后续,在这篇文章中我们将使用维基百科的文章数据比较这两个模型的准确率和召回率。概述在前一篇文章中我从定义上比较了BM25和tf-idf的...

python自动填表程序_Python的PAMIE IE自动化测试填表提交工具_weixin_39991531的博客-程序员宅基地

另外: pamie2.0 里有个模块用来处理简单的弹出窗口这类窗口的标题一般为: Microsoft Internet Explorerimport cModalPopUpa=cModalPopUp.handlePopup('Confirm',"确定") #"第二个参数是 "确定",表示弹出窗口的按钮上的文字是 "确定"这二个字如图:执行:a.run() 就可用程序来点击那个"弹出窗口"的"确定"...

windows使用Apple的Trackpad_Tristan Tsai的博客-程序员宅基地_trackpad windows

因为右手使用鼠标非常多,造成右手经常疲劳,又担心鼠标手严重,所以买了一只有出色触控体验的trackpad使用,但又发现在win上只有触摸和点击的功能。后来发现有一个国外的ExtraMagic,但需要安装驱动,且电脑必须开启测试模式,另外,很重要一点是这个软件限制了使用时间,即安装之后只能使用7天,七天之后只要电脑重启了,就不能使用,必须重新下载安装软件安装才能使用。 之前在网上一直找不到类似的软件,今天电脑又重启,提示软件过期又得重新安装,于是乎我就想度娘上看看有没有更新...

Java Eclipse的安装与汉化_郎涯技术的博客-程序员宅基地

1. 下载Eclipse      在浏览器输入网址 http://www.eclipse.org/downloads/, 在打开的界面上点击Windows 64 Bit。2. 下载中文包      在浏览器输入网址 http://www.eclipse.org/babel,在打开的界面上点击 Downloads。      点击Luna

推荐文章

热门文章

相关标签