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

【回溯+剪枝】回溯算法的概念 全排列问题

文章目录

  • 46. 全排列
  • Ⅰ. 什么是回溯算法❓❓❓
  • Ⅱ. 回溯算法的应用
    • 1、组合问题
    • 2、排列问题
    • 3、子集问题
  • Ⅲ. 解题思路:回溯 + 剪枝

在这里插入图片描述

46. 全排列

46. 全排列

​ 给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1:

输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2:

输入:nums = [0,1]
输出:[[0,1],[1,0]]

示例 3:

输入:nums = [1]
输出:[[1]]

提示:

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • nums 中的所有整数 互不相同

Ⅰ. 什么是回溯算法❓❓❓

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

​ 回溯算法的基本思想:从一个初始状态开始,按照一定的规则向前搜索,当搜索到某个状态无法前进时,回退到前一个状态,再按照其他的规则搜索。回溯算法在搜索过程中维护一个状态树,通过遍历决策树来实现对所有可能解的搜索。

​ 回溯算法的核心思想:“试错”,即在搜索过程中不断地做出选择,如果选择正确,则继续向前搜索;否则,回退到上一个状态,重新做出选择。回溯算法通常用于解决具有多个解,且每个解都需要搜索才能找到的问题,也就是相当于是 枚举

​ 其实说白了,回溯就是深搜,只不过回溯更加强调返回操作对一些题的理解是很重要的,所以专门给这种理解起了个回溯的专用词!其实回溯是有模板的,但是给出模板之后反而会限制思维,会想着怎么根据模板出发,而不是从题目本身出发,这是不行的,所以这里并不提供什么模板去背诵,当我们真正理解了回溯之后,其实写出来代码就会发现是和模板类似的!

Ⅱ. 回溯算法的应用

1、组合问题

​ 组合问题是指从给定的⼀组数(不重复)中选取出所有可能的 k 个数的组合。例如,给定数集 [1,2,3],要求选取 k=2 个数的所有组合。其结果为:

[1, 2]
[1, 3]
[2, 3]

2、排列问题

​ 排列问题是指从给定的⼀组数(可重复)中选取出所有可能的 k 个数的排列。例如,给定数集 [1,2,3],要求选取 k=2 个数的所有排列。其结果为:

[1,2]
[2,1]
[1,3]
[3,1]
[2,3]
[3,2]

3、子集问题

​ 子集问题是指从给定的一组数中选取出所有可能的子集,其中每个子集中的元素可以按照任意顺序排列。例如,给定数集 [1,2,3],要求选取所有可能的子集。其结果为:

Ⅲ. 解题思路:回溯 + 剪枝

​ 首先根据题目要求,我们 需要两个全局变量 retpathret 就是我们最后要返回的结果集,而 path 是存放当前正在走的全排列的元素!为什么要将它们设置为全局变量,而不是在函数中作为引用传递,其实是简化了函数需要填充的内容,并且在一定程度上也简化了我们的操作,尤其是后面一些题目比较说 N皇后的题目等等,如果用传引用的方式的话,其实是不太好控制的!虽说使用全局变量之后,在回溯的时候需要我们手动去恢复一下 path 的状态,但是这都是值得的!

​ 对于这类排列组合的问题,我们最好是能画出一棵详细一点的决策树(不要想的高大上,其实就是把情况枚举出来的树而已),这样子有利于帮助我们理解其中要注意的细节,如下面的图片所示!

​ 因为排列问题需要遍历所有的组合可能,包括顺序不同的组合可能,比如说 [1, 2][2, 1] 都需要满足,所以我们在排列问题中就不需要使用 index 来控制每次下一层也就是树枝之间的起始位置,只需要 每次都从数组下标为 0 开始遍历所有可能即可

在这里插入图片描述

​ 但是这里还有一个问题,就是可能会出现重复调用了某个 nums[i],比如说 [1, 2, 3] 中我们如果不对每个元素进行控制的话,可能会排列出 [1, 1, 1] 等情况,但是排列问题中我们 只能让每个元素都出现一次,所以需要使用一个 used 数组进行判断

  1. used 数组初始化为 false
  2. 因为会出现重复的情况只在一条路径上,所以我们无需担心路径之间的重复,所以我们让 used[i]false 表示是 nums[i] 还没走过,当我们在递归这条路径的下一个节点之前将 used[i] 变成 true,此时下一个节点层就会知道该 nums[i] 是走过的了,就不会再走了!然后回溯的时候将 used[i] 变成 false,这样子对同一树层是没有影响的,只会对下一层的路径产生影响!
  3. 简单地说,当我们 判断到 used[i] == true,也就说明上一层已经将这个元素遍历过了,所以我们直接 continue 即可

​ 说白了,上面的操作其实就是一个 剪枝 的操作!

​ 对于递归函数出口,我们只需要判断一下 path 数组的长度,是不是等于题目给的 nums 的长度,是的话说明当前序列已经是完成的了,则添加到 ret 结果集中然后直接返回即可!

​ 然后就是递归函数的主体,其实最重要的就是三步:

  1. 处理当前层节点(处理)
  2. 递归下一层节点(递归)
  3. 进行回溯后的处理,防止影响后面的结果(回溯)

​ 可以结合下面的代码一起分析这个过程!

class Solution {
private:vector<vector<int>> ret; // 结果集vector<int> path;        // 存放当前正在走的全排列的元素vector<bool> used;       // 标记哪个元素已经走过了,用于剪枝操作,防止重复
public:vector<vector<int>> permute(vector<int>& nums) {used.resize(nums.size(), false);dfs(nums);return ret;}void dfs(vector<int>& nums){// 递归函数出口(将当前path添加到结果集中)if(path.size() == nums.size()){ret.push_back(path);return;}for(int i = 0; i < nums.size(); ++i) // 每次都是从0开始遍历,和组合问题不一样,排列问题需要遍历所有可能{// 进行剪枝操作,防止结果重复if(used[i] == true)continue;// 处理当前层节点path.push_back(nums[i]);used[i] = true;// 递归下一层节点dfs(nums);// 进行回溯后的处理,防止影响后面的结果path.pop_back();used[i] = false;}}
};

在这里插入图片描述

相关文章:

【回溯+剪枝】回溯算法的概念 全排列问题

文章目录 46. 全排列Ⅰ. 什么是回溯算法❓❓❓Ⅱ. 回溯算法的应用1、组合问题2、排列问题3、子集问题 Ⅲ. 解题思路&#xff1a;回溯 剪枝 46. 全排列 46. 全排列 ​ 给定一个不含重复数字的数组 nums &#xff0c;返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 …...

Flutter解决macbook M芯片Android Studio中不显示IOS真机的问题

下载了最新的Android Studio LadyBug 下载了最新的xcode16.2 结果&#xff0c;只有安卓真机才在Android studio显示&#xff0c; IOS真机只在xcode显示 IOS真机不在android studio显示。 解决方法是&#xff1a; 在终端运行如下命令&#xff1a; sudo xcode-select -s /Applic…...

自签证书的dockerfile中from命令无法拉取镜像而docker的pull命令能拉取镜像

问题现象&#xff1a; docker pull images拉取镜像正常 dockerfile中的from命令拉取镜像就会报出证书错误。报错信息如下&#xff1a; [bjxtbwj-kvm-test-jenkins-6-243 ceshi_dockerfile]$ docker build . [] Building 0.4s (3/3) FINISHED …...

【MySQL】--- 复合查询 内外连接

Welcome to 9ilks Code World (๑•́ ₃ •̀๑) 个人主页: 9ilk (๑•́ ₃ •̀๑) 文章专栏&#xff1a; MySQL &#x1f3e0; 基本查询回顾 假设有以下表结构&#xff1a; 查询工资高于500或岗位为MANAGER的雇员&#xff0c;同时还要满足他们的姓名首字母为…...

QT TLS initialization failed

qt使用QNetworkAccessManager下载文件&#xff08;给出的链接可以在浏览器里面下载文件&#xff09;&#xff0c;下载失败&#xff0c; 提示“TLS initialization failed”通常是由于Qt在使用HTTPS进行文件下载时&#xff0c;未能正确初始化TLS&#xff08;安全传输层协议&…...

系统学英语 — 句法 — 复合句

目录 文章目录 目录复合句型主语从句宾语从句表语从句定语从句状语从句同位语从句 复合句型 复合句型&#xff0c;即&#xff1a;从句。在英语中&#xff0c;除了谓语之外的所有句子成分都可以使用从句来充当。 主语从句 充当主语的句子&#xff0c;通常位于谓语之前&#x…...

指针的介绍2前

1.数组名的理解 #define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h>int main() {int arr[] { 1,2,3,4,5,6,7,8,9 };printf("&arr[0] %p\n", &arr[0]);printf("arr %p\n", arr);return 0; } 观察得到&#xff0c;数组名就是数组首…...

16.Word:石油化工设备技术❗【28】

目录 题目 NO1.2 NO3 NO4 题目 NO1.2 F12&#xff1a;另存为将“Word素材.docx”文件另存为“Word. docx”&#xff08;“docx”为文件扩展名&#xff09; 光标来到表格上方→插入→形状→新建画布→单击选中→格式→高度/宽度&#xff08;格式→大小对话框→取消勾选✔锁定…...

Python-基础环境(01) 虚拟环境,Python 基础环境之虚拟环境,一篇文章助你完全搞懂!

Python的虚拟环境是一种工具&#xff0c;它能够创建一个隔离的独立Python环境。每个虚拟环境都有自己独立的Python解释器和安装的包&#xff0c;不会与其他虚拟环境或系统的全局Python环境发生冲突。虚拟环境特别适用于以下情况&#xff1a; 项目隔离&#xff1a;不同的项目可…...

Dest1ny漏洞库:用友 U8-CRM 系统 ajaxgetborrowdata.php 存在 SQL 注入漏洞

用友U8-CRM系统ajaxgetborrowdata.php存在SQL注入漏洞&#xff0c;文件多个方法存在SQL注入漏洞&#xff0c;未经身份验证的攻击者通过漏洞执行任意SQL语句&#xff0c;调用xp_cmdshell写入后门文件&#xff0c;执行任意代码&#xff0c;从而获取到服务器权限。 hunter app.n…...

java.sql.Date 弃用分析与替代方案

引言 java.sql.Date 是 Java 标准库中的一个类&#xff0c;它继承自 java.util.Date&#xff0c;主要用于在 Java 应用程序与数据库之间进行日期数据的传输。然而&#xff0c;随着 Java 语言的发展&#xff0c;java.sql.Date 以及其父类 java.util.Date 逐渐被认为存在设计缺陷…...

HarmonyOS:状态管理最佳实践

一、概述 在声明式UI编程范式中&#xff0c;UI是应用程序状态的函数&#xff0c;应用程序状态的修改会更新相应的UI界面。ArkUI采用了MVVM模式&#xff0c;其中ViewModel将数据与视图绑定在一起&#xff0c;更新数据的时候直接更新视图。如下图所示&#xff1a; ArkUI的MVVM模式…...

如何提高新产品研发效率

优化研发流程、采用先进工具、提升团队协作、持续学习与改进&#xff0c;是提高新产品研发效率的关键。其中&#xff0c;优化研发流程尤为重要。通过简化流程&#xff0c;减少不必要的环节和复杂性&#xff0c;企业可以显著提升研发效率。例如&#xff0c;采用自动化测试工具和…...

MongoDB平替数据库对比

背景 项目一直是与实时在线监测相关&#xff0c;特点数据量大&#xff0c;读写操作大&#xff0c;所以选用的是MongoDB。但按趋势来讲&#xff0c;需要有一款国产数据库可替代&#xff0c;实现信创要求。选型对比如下 1. IoTDB 这款是由清华大学主导的开源时序数据库&#x…...

JavaScript系列(46)-- WebGL图形编程详解

JavaScript WebGL图形编程详解 &#x1f3a8; 今天&#xff0c;让我们深入探讨JavaScript的WebGL图形编程。WebGL是一种基于OpenGL ES的JavaScript API&#xff0c;它允许我们在浏览器中渲染高性能的2D和3D图形。 WebGL基础概念 &#x1f31f; &#x1f4a1; 小知识&#xff…...

YOLO目标检测4

一. 参考资料 《YOLO目标检测》 by 杨建华博士 本篇文章的主要内容来自于这本书&#xff0c;只是作为学习记录进行分享。 二. 环境搭建 (1) ubuntu20.04 anaconda安装方法 (2) 搭建yolo训练环境 # 首先&#xff0c;我们建议使用Anaconda来创建一个conda的虚拟环境 conda cre…...

十三先天记

没有一刻&#xff0c;只有当下在我心里。我像星星之间的空间一样空虚。他们是我看到的第一件事&#xff0c;我知道的第一件事。 在接下来的时间里&#xff0c;我意识到我是谁&#xff0c;我是谁。我知道星星在我上方&#xff0c;星球的固体金属体在我脚下。这个支持我的世界是泰…...

【论文阅读笔记】“万字”关于深度学习的图像和视频阴影检测、去除和生成的综述笔记 | 2024.9.3

论文“Unveiling Deep Shadows: A Survey on Image and Video Shadow Detection, Removal, and Generation in the Era of Deep Learning”内容包含第1节简介、第2-5节分别对阴影检测、实例阴影检测、阴影去除和阴影生成进行了全面的综述。第6节深入讨论了阴影分析&#xff0…...

Android AOP:aspectjx

加入引用 在整个项目的 build.gradle 中&#xff0c;添加 classpath "com.hujiang.aspectjx:gradle-android-plugin-aspectjx:2.0.10" 可以看到测试demo的 gradle 版本是很低的。 基于 github 上的文档&#xff0c;可以看到原版只支持到 gradle 4.4 。后续需要使…...

前端【11】HTML+CSS+jQUery实战项目--实现一个简单的todolist

前端【8】HTMLCSSjavascript实战项目----实现一个简单的待办事项列表 (To-Do List)-CSDN博客 学过jQUery可以极大简化js代码的编写&#xff0c;基于之前实现的todolist小demo&#xff0c;了解如何使用 jQuery 来实现常见的动态交互功能。 修改后的js代码 关键点解析 动态添加…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

C++初阶-list的底层

目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

渲染学进阶内容——模型

最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍

文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结&#xff1a; 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析&#xff1a; 实际业务去理解体会统一注…...

IT供电系统绝缘监测及故障定位解决方案

随着新能源的快速发展&#xff0c;光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域&#xff0c;IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选&#xff0c;但在长期运行中&#xff0c;例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

浅谈不同二分算法的查找情况

二分算法原理比较简单&#xff0c;但是实际的算法模板却有很多&#xff0c;这一切都源于二分查找问题中的复杂情况和二分算法的边界处理&#xff0c;以下是博主对一些二分算法查找的情况分析。 需要说明的是&#xff0c;以下二分算法都是基于有序序列为升序有序的情况&#xf…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...