当前位置: 首页 > news >正文

DFS算法系列 回溯

DFS算法系列-回溯

文章目录

  • DFS算法系列-回溯
    • 1. 算法介绍
    • 2. 算法应用
      • 2.1 全排列
      • 2.2 组合
      • 2.3 子集
    • 3. 总结

1. 算法介绍

回溯算法是一种经典的递归算法,通常被用来解决排列问题、组合问题和搜索问题

基本思想

从一个初始状态开始,按一定的规则向前搜索,当搜索遇到瓶颈无法再前进时,回到当前状态的上一个状态,按照新的要求/条件继续向前搜索,直至所有可用条件都遍历完成。

简单的说就是:不撞南墙不回头

对于回溯算法,其核心就在于不断的"试错",若选择正确则继续往下搜索,否则就"回头"选择另一个选项继续往下搜索。

下面提供一个回溯算法的模板(模板只是对算法理解的总结概况,相较于没有思考的套模板,理解其中的算法思想更加重要–>通过做题积累)

List<List<Integer>> ret;
List<Integer> path; void dfs(int[] nums, ...) {// 满⾜结束条件if (/* 满⾜结束条件 */) {// 将路径添加到结果集中ret.add(new ArrayList<>(path));return;}// 遍历所有选择for (int i = 0;i < nums.size();i++) {// 做出选择path.add(nums[i]);  // 做出当前选择后继续搜索dfs(path, nums);// 恢复现场path.remove(path.size() - 1);}
}

其中path用来记录每次选择后改变的路径nums[i]表示当前做出的选择,并且在当前选择满足递归结束条件后,将当前路径添加到结果集中,结束当前层递归并恢复现场,即恢复刚刚完成修改的路径到上一个状态,才能继续处理当前层的另一个选择,如下图所示:

在这里插入图片描述

了解完回溯算法,我们来做一些相关的算法题加深印象!

2. 算法应用

对于回溯(以及DFS相关的题),建议的解题步骤:

  1. 先画决策树
  2. 根据决策树编写函数体,可设置全局变量、添加剪枝提高效率;
  3. 找到递归出口

2.1 全排列

题目链接:[全排列]

决策树

在这里插入图片描述

代码示例

class Solution {List<List<Integer>> ret;List<Integer> path;boolean[] check;public List<List<Integer>> permute(int[] nums) {ret = new ArrayList<>();path = new ArrayList<>();check = new boolean[nums.length];dfs(nums);return ret;}void dfs(int[] nums) {if (path.size() == nums.length) {ret.add(new ArrayList(path));return;}for (int i = 0;i < nums.length;i++) { // 这里让i=0,使下一层选项依旧为所有情况(1,2,3,4)if (!check[i]) { // check数组用来记录当前数字是否被使用check[i] = true;   path.add(nums[i]); // 将数字添加到路径中dfs(nums);check[i] = false;path.remove(path.size() - 1);}}}
}

2.2 组合

题目链接:[组合]

决策树:

在这里插入图片描述

代码示例

class Solution {List<List<Integer>> ret;List<Integer> path;boolean[] check;int len;int pre;public List<List<Integer>> combine(int n, int k) {ret = new ArrayList<>();path = new ArrayList<>();check = new boolean[n + 1];len = k;int[] nums = new int[n + 1];for (int i = 1;i <= n;i++) {nums[i] = i;}dfs(nums, 1);return ret;}public void dfs(int[] nums, int pos) {if (path.size() == len) { // 当路径长度和要求的组合数相等时返回ret.add(new ArrayList<>(path));return;}for (int i = pos;i <= nums.length - 1;i++) { // 这里让i=pos,使下一层选项不会出现当前数字,并且下层选项从pos+1开始if (!check[i]) {	path.add(nums[i]);  check[i] = true;dfs(nums, i + 1);path.remove(path.size() - 1);check[i] = false;}}}
}

注:这里让i=pos,使下一层选项不会出现当前数字,并且下层选项从pos+1开始若为i = 0,则使下一层选项依旧为所有情况(1,2,3)

在这里插入图片描述

2.3 子集

题目链接:[子集]

决策树

在这里插入图片描述

代码示例

class Solution {static List<List<Integer>> ret;static List<Integer> path;public List<List<Integer>> subsets(int[] nums) {ret = new ArrayList<>();path = new ArrayList<>();dfs(nums, 0);return ret;}public void dfs(int[] nums, int cur) {ret.add(new ArrayList<>(path)); // 此处不设出口目的是将每个节点路径都添加到ret中for (int i = cur;i < nums.length;i++) { // 这里让i=cur,使下一层选项不会出现当前数字,并且下层选项从cur+1开始path.add(nums[i]);dfs(nums, i + 1);path.remove(path.size() - 1); }}
}

3. 总结

总的来说,回溯就是不断的"试错"并回头进行新的选择,和回溯相关的题就要把决策树画出来,通过它来找到我们的递归出口并编写函数体(注意for循环中起始标的使用),注意记得恢复现场哦!

相关文章:

DFS算法系列 回溯

DFS算法系列-回溯 文章目录 DFS算法系列-回溯1. 算法介绍2. 算法应用2.1 全排列2.2 组合2.3 子集 3. 总结 1. 算法介绍 回溯算法是一种经典的递归算法&#xff0c;通常被用来解决排列问题、组合问题和搜索问题 基本思想 从一个初始状态开始&#xff0c;按一定的规则向前搜索&…...

Linux C应用编程:MQTT物联网

1 MQTT通信协议 MQTT&#xff08;Message Queuing Telemetry Transport&#xff0c;消息队列遥测传 输&#xff09;是一种基于客户端-服务端架构的消息传输协议&#xff0c;如今&#xff0c;MQTT 成为了最受欢迎的物联网协议&#xff0c;已广泛应用于车联网、智能家居、即时聊…...

企业常用Linux文件命令相关知识+小案例

远程连接工具无法连接VMWARE&#xff1a; 如果发现连接工具有时连不上&#xff0c;ip存在&#xff0c;这时候我们查看网络编辑器&#xff0c;更多配置&#xff0c;看vnet8是不是10段&#xff0c;nat设置是否是正确的&#xff1f; 软件重启一下虚机还原一下网络编辑器 查看文件…...

Istio介绍

1.什么是Istio Istio是一个开源的服务网格&#xff08;Service Mesh&#xff09;框架&#xff0c;它提供了一种简单的方式来为部署在Kubernetes等容器编排平台上的微服务应用添加网络功能。Istio的核心功能包括&#xff1a; 服务治理&#xff1a;Istio能够帮助管理服务之间的…...

代码随想录算法训练营第四十七天|leetcode115、392题

一、leetcode第392题 本题要求判断s是否为t的子序列&#xff0c;因此设置dp数组&#xff0c;dp[i][j]的含义是下标为i-1的子串与下标为j-1的子串相同字符的个数&#xff0c;可得递推公式是通过s[i-1]和t[j-1]是否相等区分。 具体代码如下&#xff1a; class Solution { publ…...

将Ubuntu18.04默认的python3.6升级到python3.8

1、查看现有的 python3 版本 python3 --version 2、安装 python3.8 sudo apt install python3.8 3、将 python3.6 和 3.8 添加到 update-alternatives sudo update-alternatives --install /usr/bin/python3 python3 /usr/bin/python3.6 1 sudo update-alternatives --insta…...

Python和Java哪个更适合后端开发?

Python和Java都是强大的后端开发语言&#xff0c;它们各自有鲜明的特点和适用场景。选择哪一个更适合后端开发&#xff0c;主要取决于具体的项目需求、团队技术栈、个人技能偏好以及长期发展考虑等因素。 下面是两者在后端开发中的优势和劣势&#xff1a; 「Python&#xff1…...

Python+pytest接口自动化之cookie绕过登录(保持登录状态)

前言 我们今天来聊聊pythonpytest接口自动化之cookie绕过登录&#xff08;保持登录状态&#xff09;&#xff0c;在编写接口自动化测试用例或其他脚本的过程中&#xff0c;经常会遇到需要绕过用户名/密码或验证码登录&#xff0c;去请求接口的情况&#xff0c;一是因为有时验证…...

什么数据集成(Data Integration):如何将业务数据集成到云平台?

说到数据集成&#xff08;Data Integration&#xff09;&#xff0c;简单地将所有数据倒入数据湖并不是解决办法。 在这篇文章中&#xff0c;我们将介绍如何轻松集成数据、链接不同来源的数据、将其置于合适的环境中&#xff0c;使其具有相关性并易于使用。 数据集成&#xff1…...

国外EDM邮件群发多少钱?哪个软件好?

在当今全球化市场环境下&#xff0c;电子邮件营销作为最有效的数字营销渠道之一&#xff0c;其影响力不容忽视。而高效精准的EDM&#xff08;Electronic Direct Mail&#xff09;邮件营销策略更是企业拓展海外市场、提升品牌知名度的关键手段。云衔科技以其创新的智能EDM邮件营…...

C语言入门算法——回文数

题目描述&#xff1a; 若一个数&#xff08;首位不为零&#xff09;从左向右读与从右向左读都一样&#xff0c;我们就将其称之为回文数。 例如&#xff1a;给定一个十进制数 56&#xff0c;将 56 加 65&#xff08;即把 56 从右向左读&#xff09;&#xff0c;得到 121 是一个…...

OceanBase—操作实践

文档结构 1、概念简介2、核心设计3、操作实践3.3、数据同步 官方文档&#xff1a;https://www.oceanbase.com/docs/oceanbase-database-cn 1、概念简介 版本分为社区版和企业版&#xff0c;其中企业版兼容MySQL 和Oracle数据库语法&#xff1b; 2、核心设计 存储层 复制层 …...

智慧用电安全管理系统

智慧用电安全管理系统 智慧用电安全管理系统是智能电网中客户侧关键的构成部分&#xff0c;是基本建设新型智慧城市的基本&#xff0c;将完成地区内各种各样用电设备的智能化系统监管&#xff0c;完成地区内日常生活与工作中安全性、舒服。 一、智慧用电安全管理系统介绍 …...

Rust语言入门第二篇-Cargo教程

文章目录 Rust语言入门第二篇-Cargo教程一&#xff0c;Cargo 是什么二&#xff0c;Cargo教程Cargo.toml文件src/main.rs 文件构建并运行Cargo项目 Rust语言入门第二篇-Cargo教程 本节提供对cargo命令行工具的快速了解。我们演示了它为我们生成新包的能力&#xff0c;它在包内编…...

测试用例的编写方式

学习目标 能对穷举场景设计测试点能对限定边界规则设计测试点能对多条件依赖关系进行设计测试点能对于项目业务进行设计测试点 目录 等价类划分法案例 等价类划分 说明&#xff1a;在所有测试数据中&#xff0c;具有某种共同特征的数据集合进行划分分类&#xff1a; 有效等…...

HarmonyOS实战开发-状态管理、通过使用页面级的状态变量 和应用级的状态变量 来实现应用的状态管理。

介绍 本示例通过使用页面级的状态变量 和应用级的状态变量 来实现应用的状态管理。 效果预览 使用说明 1.点击首页中的基本类型进入对应页面&#xff0c;点击按钮可以更改圆形的颜色&#xff1b;点击查看源码可以展示基本类型功能效果的源码。 2.点击首页中的数组类型进入对…...

【Java开发指南 | 第二篇】标识符、Java关键字及注释

专栏&#xff1a;Java开发指南 CSDN秋说 文章目录 标识符Java关键字Java注释 标识符 Java 所有的组成部分都需要名字。类名、变量名以及方法名都被称为标识符。 所有的标识符都应该以字母&#xff08;A-Z 或者 a-z&#xff09;,美元符&#xff08;$&#xff09;、或者下划线&…...

3D可视化技术:研发基地的科技新篇章

在科技日新月异的今天&#xff0c;我们生活在一个充满无限可能性的时代。而在这个时代中&#xff0c;3D可视化技术正以其独特的魅力&#xff0c;引领着科技领域的新一轮变革。 3D可视化技术通过三维图像的方式&#xff0c;将现实世界或虚拟世界中的物体、场景等以立体、逼真的形…...

蓝旭前端05:JavaScript进阶

蓝旭前端05&#xff1a;JavaScript进阶 基础简单复习 数据类型 基本数据类型&#xff1a;Number、String、Boolean、Null、Undefined等。引用数据类型&#xff1a;Object、Array、Function等。typeof操作符&#xff1a;返回数据类型的字符串形式。 变量 变量声明&#xff1…...

【docker-compose】安装及配置

目录 安装在线安装离线安装 配置mysql5.7bitnami/mysql8.3redisweb前后台分离部署前端https(SSL)配置nginx动态传参资源限制&#xff1a;内存、cpunacossentinelgateway 问题汇总iptables No chain/target/match by that namedocker-compose.yml修改mysql密码&#xff0c;重启后…...

【第十五届】蓝桥杯省赛C++b组

今年的蓝桥杯省赛已经结束了&#xff0c;与以往不同&#xff0c;今年又回到了8道题&#xff0c;而22&#xff0c;23年出现了10道题 大家觉得难度怎么样&#xff0c;欢迎进来讨论&#xff0c;博主今年没参加哈&#xff0c;大家聊聊&#xff0c;我听听大家的意见和看法哈 试题A:…...

thinkphp6 Driver [Think] not supported.

问题的原因&#xff1a;使用view这个类但相应的库未安装&#xff08;新版仅内置了PHP原生模板引擎&#xff09; 官方解释&#xff1a;视图功能由\think\View类配合视图驱动&#xff08;也即模板引擎驱动&#xff09;类一起完成&#xff0c;新版仅内置了PHP原生模板引擎&#x…...

爱自然生命力专项基金:“爱·启航”残障家庭教育援助项目帮扶上万残障家庭

为进一步积极践行社会责任&#xff0c;助力公益慈善事业&#xff0c;2017年2月爱自然生命力体系与中国下一代教育基金会开展相关合作&#xff0c;共同启动了中国下一代教育基金会爱自然生命力专项基金&#xff0c;并启动了基金第一个项目“爱启航残障家庭教育援助项目”&#x…...

【ubuntu】如何追加path

【背景】 在ubuntu上整备一个项目环境时需要追加Path。 【方法】 先复制下需要加的Path&#xff0c;比如我的是&#xff1a;/home/sheep431/.local/bin 加path命令 nano ~/.bashrc在nano界面输入如下命令 export PATH"/home/sheep431/.local/bin:$PATH"【检验】…...

用html写一个有趣的鬼魂动画

<!DOCTYPE html> <html lang"en" > <head><meta charset"UTF-8"><title>一个有趣的鬼魂动画</title><link rel"stylesheet" href"https://cdnjs.cloudflare.com/ajax/libs/meyer-reset/2.0/reset.m…...

【C++软件调试技术】C++软件开发维护过程中典型调试问题的解答与总结

目录 1、引发C软件异常的常见原因有哪些&#xff1f; 2、排查C软件异常的常用方法有哪些&#xff1f; 3、为什么要熟悉常见的异常内存地址&#xff1f; 4、调试时遇到调用IsBadReadPtr或者IsBadWritePtr引发的异常&#xff0c;该如何处理&#xff1f; 5、如何排查GDI对象泄…...

Pygame经典游戏:贪吃蛇

------------★Pygame系列教程★------------ Pygame经典游戏&#xff1a;贪吃蛇 Pygame教程01&#xff1a;初识pygame游戏模块 Pygame教程02&#xff1a;图片的加载缩放旋转显示操作 Pygame教程03&#xff1a;文本显示字体加载transform方法 Pygame教程04&#xff1a;dra…...

推荐一个免费使用Claude 3, GPT4和Gemini 1.5 Pro的网站

在探索人工智能的广阔天地时,我偶然间发现了You AI这一平台,它不仅更新了大量的模型,还慷慨地提供了免费的使用机会。兴奋之余,我迅速开始尝试这些新功能,并决定将我的体验分享给大家。以下是我试用的流程: 打开网站:点击左下角的Sign in蓝色框 https://you.comhttps://…...

An Investigation of Geographic Mapping Techniques for Internet Hosts(2001年)第二部分

​下载地址:An investigation of geographic mapping techniques for internet hosts | Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications 被引次数:766 Padmanabhan V N, Subramanian L. An i…...

解锁生成式 AI 的力量:a16z 提供的 16 个企业指南

企业构建和采购生成式AI方面的16项改变 生成式 AI 领域趋势洞察&#xff1a;企业构建和采购生成式 AI 的方式正在发生重大转变&#xff0c;具体表现在&#xff1a;* 专注于可信度和安全性&#xff1a;75% 的企业将信任和安全性视为关键因素。* 优先考虑可扩展性和灵活性&#x…...

nas做网站服务器/今天发生的重大新闻

写在前面 官方文档地址 ES 的查询语言称为 DSL 即 Domain Specific Language 领域专用语言。 本文查询将以下列索引结构为例子展开。 PUT /dying_gq_bookstore {"mappings": {"properties": {"book_id": {"type": "long"…...

邓亚萍近况 做网站败光20亿/宁德市疫情最新消息

Edit笔记内容&#xff1a;Python3 OS 文件/目录方法 笔记日期&#xff1a;2017-11-12Python3 OS 文件/目录方法os 模块提供了非常丰富的方法用来处理文件和目录。常用的方法如下表所示&#xff1a;声明&#xff1a;转自以下网址&#xff1a; http://www.runoob.com/python3/pyt…...

泰州企业建站程序/产品推广文案范例

您将希望使用LinuxPAM来允许您使用面部识别进行Su/Sudo。我用pythonbash脚本完成了这项工作&#xff1a;https://github.com/lambrou/susentry我已经完成了自述的一部分&#xff0c;并将结合你的问题向你解释。在您需要做的第一件事是制作一个bash脚本来调用python脚本。在#!/b…...

旅游公司网站建设/seo是什么意思中文

公司是个电子商务网站,电子商务网站就要涉及到订单的处理及物流费用的统计.这里暂时说下物流费用的统计,订单的处理很早前就想写了,只是太懒惰了,呵呵.事先声明一下,本人只是新手,发的文章是希望大家指点的,光拍砖不给建议的,怕怕哦~~ 先大概说下公司的情况,也好让大家明白…...

安徽建设相关网站/互联网优化

解决办法&#xff1a;换上usb接口&#xff0c;舍弃esata, 重新上电&#xff0c;就能识别了 转载于:https://www.cnblogs.com/norsd/archive/2012/03/12/6359474.html...

商城网站哪个公司做的好处/民生热点新闻

过去&#xff0c;我们的电脑只限于一个操作系统&#xff0c;如果我们不想从头开始安装另一个操作系统(冒着丢失我们所有宝贵数据的风险)&#xff0c;那么我们无能为力。由于资金限制或物理空间限制&#xff0c;我们并非所有人都能买得起多台电脑&#xff0c;在这种情况下&#…...