代码随想录阅读笔记-回溯【全排列】

题目

给定一个 没有重复 数字的序列,返回其所有可能的全排列。

示例

  • 输入: [1,2,3]
  • 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

思路 

以[1,2,3]为例,抽象成树形结构如下:

46.全排列

回溯三部曲

1、递归函数参数

首先排列是有序的,也就是说 [1,2] 和 [2,1] 是两个集合,这和之前分析的子集以及组合所不同的地方

可以看出元素1在[1,2]中已经使用过了,但是在[2,1]中还要在使用一次1,所以处理排列问题就不用使用startIndex了。但排列问题需要一个used数组,标记已经选择的元素,如图橘黄色部分所示:

46.全排列

代码如下:

vector<vector<int>> result;
vector<int> path;
void backtracking (vector<int>& nums, vector<bool>& used)

2、递归终止条件

46.全排列

可以看出叶子节点,就是收割结果的地方。

那么什么时候,算是到达叶子节点呢?

当收集元素的数组path的大小达到和nums数组一样大的时候,说明找到了一个全排列,也表示到达了叶子节点。

代码如下:

// 此时说明找到了一组
if (path.size() == nums.size()) {
    result.push_back(path);
    return;
}

3、单层搜索的逻辑

这里和之前问题最大的不同就是for循环里不用startIndex了。

因为排列问题,每次都要从头开始搜索,例如元素1在[1,2]中已经使用过了,但是在[2,1]中还要再使用一次1。

而used数组,其实就是记录此时path里都有哪些元素使用了,一个排列里一个元素只能使用一次

代码如下:

for (int i = 0; i < nums.size(); i++) {
    if (used[i] == true) continue; // path里已经收录的元素,直接跳过
    used[i] = true;
    path.push_back(nums[i]);
    backtracking(nums, used);
    path.pop_back();
    used[i] = false;
}

整体C++代码如下:

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking (vector<int>& nums, vector<bool>& used) {
        // 此时说明找到了一组
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (used[i] == true) continue; // path里已经收录的元素,直接跳过
            used[i] = true;
            path.push_back(nums[i]);
            backtracking(nums, used);
            path.pop_back();
            used[i] = false;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        result.clear();
        path.clear();
        vector<bool> used(nums.size(), false);
        backtracking(nums, used);
        return result;
    }
};
  • 时间复杂度: O(n!)
  • 空间复杂度: O(n)

大家此时可以感受出排列问题的不同:

  • 每层都是从0开始搜索而不是startIndex
  • 需要used数组记录path里都放了哪些元素了

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/546499.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

C++内存分布

C代码编译过程 预处理 宏定义展开、头文件展开、条件编译&#xff0c;这里并不会检查语法编译检查语法&#xff0c;将预处理后文件编译生成汇编文件汇编将汇编文件生成目标文件(二进制文件)链接将目标文件链接为可执行程序 进程的内存分布 程序运行起来(没有结束前)就是一个…

Java实现单点登录(SSO)详解:从理论到实践

✨✨谢谢大家捧场&#xff0c;祝屏幕前的小伙伴们每天都有好运相伴左右&#xff0c;一定要天天开心哦&#xff01;✨✨ &#x1f388;&#x1f388;作者主页&#xff1a; 喔的嘛呀&#x1f388;&#x1f388; ✨✨ 帅哥美女们&#xff0c;我们共同加油&#xff01;一起进步&am…

亚信安慧AntDB:为安全加码

亚信安慧AntDB分布式数据库凭借平滑扩展、高可用性和低成本三大核心优势&#xff0c;在业界获得了极高的评价和认可。这些优点不仅为AntDB提供了巨大的市场发展潜力&#xff0c;也使其成为众多企业在数据管理上的首选解决方案。 AntDB的平滑扩展特性极大地提升了企业的灵活性和…

内网渗透-内网环境下的横向移动总结

内网环境下的横向移动总结 文章目录 内网环境下的横向移动总结前言横向移动威胁 威胁密码安全 威胁主机安全 威胁信息安全横向移动威胁的特点 利用psexec 利用psexec.exe工具msf中的psexec 利用windows服务 sc命令 1.与靶机建立ipc连接2.拷贝exe到主机系统上3.在靶机上创建一个…

EasyRecovery数据恢复软件2024百度云网盘下载链接

EasyRecovery数据恢复软件是一款功能强大的数据恢复工具&#xff0c;它能够帮助用户从各种存储设备中恢复丢失或误删除的文件数据。无论是由于意外删除、格式化、病毒攻击还是其他原因导致的数据丢失&#xff0c;EasyRecovery都能提供有效的解决方案。 该软件支持多种存储介质…

JavaScript排序大揭秘:手绘图解6大常见排序算法,一网打尽

前言 &#x1f4eb; 大家好&#xff0c;我是南木元元&#xff0c;热爱技术和分享&#xff0c;欢迎大家交流&#xff0c;一起学习进步&#xff01; &#x1f345; 个人主页&#xff1a;南木元元 本文用图解总结梳理了6种常见的排序算法 &#xff0c;如下&#x1f447;&#xff1…

地理空间分析中的深度学习应用

深度学习与地理信息系统 (GIS) 的结合彻底改变了地理空间分析和遥感的格局。这种结合将遥感和地理空间分析领域带到了全球研究人员和科学家的前沿。 深度学习是机器学习的一个复杂子集&#xff08;更多关于机器学习的内容&#xff0c;请参阅我的其他文章&#xff09;&#xff0…

Qt5 编译oracle数据库驱动

库文件 1、Qt源码目录&#xff1a;D:\Qt5\5.15.2\Src\qtbase\src\plugins\sqldrivers\oci 2、oracle客户端SDK: https://www.oracle.com/database/technologies/instant-client/winx64-64-downloads.html 下载各版本中的如下压缩包&#xff0c;一定要版本相同的 将两个压缩包…

如何通过WordPress发送电子邮件

本周有一个客户&#xff0c;购买Hostease的HK Basic Linux虚拟主机&#xff0c;询问我们的在线客服&#xff0c;WordPress发送电子邮件不成功。我们为用户提供教程&#xff0c;用户很快完成了设置。在此&#xff0c;我们分享这个操作教程&#xff0c;希望可以对您有帮助。 Host…

github上的软件许可证是什么?如何合并本地的分支德语难学还是俄语更加难学?站在一个中国人的立场上,德语难学还是俄语更加难学?俄语跟德语有什么样的显著差别?

目录 github上的软件许可证是什么&#xff1f; 如何合并本地的分支 德语难学还是俄语更加难学&#xff1f; 站在一个中国人的立场上&#xff0c;德语难学还是俄语更加难学&#xff1f; 俄语跟德语有什么样的显著差别&#xff1f; github上的软件许可证是什么&#xff1f; …

深入剖析Tomcat(二) 实现一个简单的Servlet容器

现在开始《深入剖析Tomcat》第二章的内容&#xff0c;第一章中&#xff0c;我们编码实现了一个能正常接收HTTP请求并返回静态资源的Web容器&#xff0c;这一章开始引入Servlet的概念&#xff0c;使我们的服务能根据请求动态返回内容。 Servlet是什么&#xff1f; 这是首先要弄…

Linux基础|线程池Part.1|线程池的定义和运行逻辑

线程池的定义和运行逻辑 多线程的问题&#xff1a; 如果并发的线程数量很多&#xff0c;并且每个线程都是执行一个时间很短的任务就结束了&#xff0c;这样频繁创建线程就会大大降低系统的效率&#xff0c;因为频繁创建线程和销毁线程需要时间。 那么一个很自然的想法就出现了…

杂货铺 | Linux虚拟机Ubuntu操作系统下设置共享文件夹(以及找不到hgfs文件夹怎么办)

文章目录 &#x1f4da;步骤一&#xff1a;配置共享文件夹&#x1f4da;步骤二&#xff1a;配置挂载环境&#x1f4da;步骤三&#xff1a;解决权限问题&#x1f4da;步骤四&#xff1a;解决重启失效问题 &#x1f4da;步骤一&#xff1a;配置共享文件夹 建立本地共享文件夹&…

Mysql的事务隔离级别以及事务的四大特性。

MySQL 的事务隔离级别是数据库管理系统中的一个重要概念&#xff0c;它决定了事务如何隔离和影响其他并发事务。MySQL 支持四种事务隔离级别&#xff0c;分别是&#xff1a;读未提交&#xff08;READ UNCOMMITTED&#xff09;、读已提交&#xff08;READ COMMITTED&#xff09;…

Qt QStyle详解

1.简介 QStyle类是 Qt 框架中用于控制应用程序界面元素外观的一个抽象基类。这个类提供了一种方式来定制窗口部件&#xff08;widgets&#xff09;的绘制和行为&#xff0c;可以通过改变主题或风格来更改应用程序的外观&#xff0c;而无需修改窗口部件本身的代码。 Qt包含一组…

一种基于OpenCV的图片倾斜矫正方法

需求描述&#xff1a; 对倾斜的图片进行矫正&#xff0c;返回倾斜角度和矫正后的图片。 解决方法&#xff1a; 1、各种角度点被投影到一个累加器阵列中&#xff0c;其中倾斜角度可以定义为在最大化对齐的搜索间隔内的投影角度。 2、以不同的角度旋转图像&#xff0c;并为每…

Excel文件解析

在此模块的学习中&#xff0c;我们需要一个新的开源类库---Apahche POI开源类库。这个类库的用途是&#xff1a;解析并生成Excel文件(Word、ppt)。Apahche POI基于DOM方式进行解析&#xff0c;将文件直接加载到内存&#xff0c;所以速度比较快&#xff0c;适合Excel文件数据量不…

学习经验分享【32】本科/硕士开题报告、中期报告等写作经验分享

本科/硕士阶段首先就是要写开题报告&#xff0c;然后中期报告&#xff0c;这篇博文就是分享一下写报告的经验&#xff0c;避免被老师打回来。本人有丰富的写报告经验&#xff0c;有需要的朋友可添加文末联系方式与我联系。 一、本科开题报告的提纲 课题来源及研究的目的和意义…

js性能优化(五)

第五章开始啦~~~~~~~~~~~~~ 防抖和节流之前自己有学过一次&#xff0c;包括几种方式怎么实现&#xff0c;代码如何写花了两天有写过&#xff0c;这次算是更系统的一个复习加填补 十七、防抖与节流 为什么需要防抖和节流&#xff1a; 在一些高频率事件触发的场景下我们不希望…

51单片机

STC89C52 一.定时器 1.介绍 2.计时 2.定时器寄存器  2.1 定时器控制寄存器TCON  2.2 定时器模式寄存器TMOD  2.3 定时器如何定时10毫秒  2.4 定时器寄存器配置    2.4.1 TCON    2.4.2 TMOD    2.4.3 实现    2.4.5 按位操作 3.定时器中断  3.1 定…