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

力扣热题100_回溯_78_子集

文章目录

  • 题目链接
  • 解题思路
  • 解题代码


题目链接

78. 子集

给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

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

示例 2:
输入:nums = [0]
输出:[[],[0]]

解题思路

回溯算法
下面我们根据回溯算法三步走,写出对应的回溯算法。

  • 1.明确所有选择:根据数组中每个位置上的元素选与不选两种选择。
  • 2.明确终止条件:当遍历到决策树的叶子节点时,就终止了。即当前路径搜索到末尾时,递归终止。
  • 3.将决策树和终止条件翻译成代码:
    • 定义回溯函数:
      • backtracking(nums, index): 函数的传入参数是 nums(可选数组列表)和 index(代表当前正在考虑元素是 nums[i] ),全局变量是 res(存放所有符合条件结果的集合数组)和 path(存放当前符合条件的结果)。
      • backtracking(nums, index): 函数代表的含义是:在选择 nums[index] 的情况下,递归选择剩下的元素。
    • 书写回溯函数主体(给出选择元素、递归搜索、撤销选择部分)。
      • 从当前正在考虑元素,到数组结束为止,枚举出所有可选的元素。对于每一个可选元素:
        • 约束条件:之前选过的元素不再重复选用。每次从 index 位置开始遍历而不是从 0 位置开始遍历就是为了避免重复。集合跟全排列不一样,子集中 {1, 2} 和 {2, 1} 是等价的。为了避免重复,我们之前考虑过的元素,就不再重复考虑了。

        • 选择元素:将其添加到当前子集数组 path 中。

        • 递归搜索:在选择该元素的情况下,继续递归考虑下一个位置上的元素。

        • 撤销选择:将该元素从当前子集数组 path 中移除。

            for i in range(index, len(nums)):   # 枚举可选元素列表path.append(nums[i])            # 选择元素backtracking(nums, i + 1)       # 递归搜索path.pop()                      # 撤销选择
          
    • 明确递归终止条件(给出递归终止条件,以及递归终止时的处理方法)。
      • 当遍历到决策树的叶子节点时,就终止了。也就是当正在考虑的元素位置到达数组末尾(即 start >= len(nums))时,递归停止。
      • 从决策树中也可以看出,子集需要存储的答案集合应该包含决策树上所有的节点,应该需要保存递归搜索的所有状态。所以无论是否达到终止条件,我们都应该将当前符合条件的结果放入到集合中。

解题代码

class Solution:def subsets(self, nums: List[int]) -> List[List[int]]:res = []  # 存放所有符合条件结果的集合path = []  # 存放当前符合条件的结果def backtracking(nums, index):          # 正在考虑可选元素列表中第 index 个元素res.append(path[:])                 # 将当前符合条件的结果放入集合中if index >= len(nums):              # 遇到终止条件(本题)returnfor i in range(index, len(nums)):   # 枚举可选元素列表path.append(nums[i])            # 选择元素backtracking(nums, i + 1)       # 递归搜索path.pop()                      # 撤销选择backtracking(nums, 0)return res

参考资料:datawhalechina

相关文章:

力扣热题100_回溯_78_子集

文章目录 题目链接解题思路解题代码 题目链接 78. 子集 给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 示例 1: 输入&#xff…...

浏览器如何工作(一)进程架构

分享cosine 大佬,版权©️大佬所有 浏览器的核心功能 浏览器,“浏览” 是这个产品的核心,浏览无非分为两步: 获取想浏览的资源 展示得到的资源 现代浏览器还增加了交互功能,这涉及到脚本运行。因此&#xff0c…...

【LeetCode】两数之和

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案,并且你不能使用两次相同的元素。 你可以按任意顺序返回答案。 示例 1…...

UE5学习笔记11-为拿取武器添加动画

一、一点说明 动画实例通过扩展为所有机器上的每个字符都存在动画蓝图,动画实例只能访问该计算机上的变量。 二、思路 我在武器组件中有一个武器类的指针,判断当前指针是否为空去判断当前角色是否装备武器 三、实现 1.在角色C类中添加是否装备武器的函…...

68. 文本左右对齐【 力扣(LeetCode) 】

一、题目描述 给定一个单词数组 words 和一个长度 maxWidth ,重新排版单词,使其成为每行恰好有 maxWidth 个字符,且左右两端对齐的文本。 你应该使用 “贪心算法” 来放置给定的单词;也就是说,尽可能多地往每行中放置单…...

【中等】 猿人学web第一届 第6题 js混淆-回溯

文章目录 请求流程请求参数 加密参数定位r() 方法z() 方法 加密参数还原JJENCOde js代码加密环境检测_n("jsencrypt")12345 计算全部中奖的总金额请求代码注意 请求流程 请求参数 打开 调试工具,查看数据接口 https://match.yuanrenxue.cn/api/match/6 请…...

低、中、高频率段具体在不同应用中的范围是多少

1、低频率段(Low Frequency Range) ①建筑声学和噪声控制:通常将20 Hz 到 200 Hz 的频率范围视为低频段。在这一范围内,声音的波长较长,通常与低音(如重低音音乐)和建筑结构中的振动有关。 ②…...

Oxford Model600 Model400低温氦压缩机cryogenic helium compressor手侧

Oxford Model600 Model400低温氦压缩机cryogenic helium compressor手侧...

Golang面试题四(并发编程)

目录 1.Go常见的并发模型 2.哪些方法安全读写共享变量 3.如何排查数据竞争问题 ​4.Go有哪些同步原语 1. Mutex (互斥锁) 2. RWMutex (读写互斥锁) 3. Atomic 3.1.使用场景 3.2.整型操作 3.3.指针操作 3.4.使用示例 4. Channel 使用场景 使用示例 5. sync.WaitGr…...

计算机学生高效记录并整理编程学习笔记的方法

哪些知识点需要做笔记? 以下是我认为计算机学生大学四年可以积累的笔记。 ① 编程语言类(C语言CJava):保留课堂笔记中可运行的代码部分,课后debug跑一跑。学习语言初期应该多写代码(从仿写到自己写&#…...

【书生大模型实战】L2-LMDeploy 量化部署实践闯关任务

一、关卡任务 基础任务(完成此任务即完成闯关) 使用结合W4A16量化与kv cache量化的internlm2_5-7b-chat模型封装本地API并与大模型进行一次对话,作业截图需包括显存占用情况与大模型回复,参考4.1 API开发(优秀学员必做)使用Func…...

《编程学习笔记之道:构建知识宝库的秘诀》

在编程的浩瀚世界里,我们如同勇敢的探险家,不断追寻着知识的宝藏。而高效的笔记记录和整理方法,就像是我们手中的指南针,指引着我们在这片知识海洋中前行,不至于迷失方向。在这篇文章中,我们将深入探讨如何…...

DETR论文,基于transformer的目标检测网络 DETR:End-to-End Object Detection with Transformers

transformer的基本结构: encoder-decoder的基本流程为: 1)对于输入,首先进行embedding操作,即将输入映射为向量的形式,包含两部分操作,第一部分是input embedding:例如,在NLP领域&…...

untiy有渲染线程和逻辑线程嘛

之前我也这么认为,其实unity引擎是单线程的,当然后续的jobs不在考虑范围内 如果你在一个awake 或者 start方法中 延时,是会卡住主线程的 比如 其实游戏引擎有一个基础简单理解,那就是不断的进行一个循环,在这个周期循…...

什么是数据仓库ODS层?为什么需要ODS层?

在大数据时代,数据仓库的重要性不言而喻。它不仅是企业数据存储与管理的核心,更是数据分析与决策支持的重要基础。而在数据仓库的各个层次中,ODS层(Operational Data Store,操作型数据存储)作为关键一环&am…...

permutation sequence(

60. Permutation Sequence class Solution:def getPermutation(self, n: int, k: int) -> str:def rec(k, l, ans, n):if(n0): return# 保留第一个位置,剩下数字的组合leftCom math.factorial(n - 1) #用于计算 (n-1) 的阶乘值ele k // leftCommod k % leftCo…...

PCL 三线性插值

文章目录 一、简介二、实现代码三、实现效果参考资料一、简介 三线性插值是一种在三维空间中使用已知数据点进行插值的方法。它是在立方体内的插值方法,通过利用立方体的八个顶点的已知值来估算立方体内任意一点的值。三线性插值扩展了一维的线性插值和二维的双线性插值。其基…...

JVM虚拟机(一)介绍、JVM内存模型、JAVA内存模型,堆区、虚拟机栈、本地方法栈、方法区、常量池

目录 学习JVM有什么用、为什么要学JVM? JVM是什么呢? 优点一:一次编写,到处运行。(Write Once, Run Anywhere,WORA) 优点二:自动内存管理,垃圾回收机制。 优点三&am…...

Python利用xlrd复制一个Excel中的sheet保留原格式创建一个副本(注:xlrd只能读取xls)

目录 专栏导读库的介绍库的安装完整代码总结 专栏导读 🌸 欢迎来到Python办公自动化专栏—Python处理办公问题,解放您的双手 🏳️‍🌈 博客主页:请点击——> 一晌小贪欢的博客主页求关注 👍 该系列文…...

40、Python之面向对象:扩展的对象属性解析顺序(描述符 + MRO)

引言 在上一篇文章中,我们简单回顾了Python中在继承语境下的属性解析顺序,同时补充了能够控制、影响属性解析的3个函数/方法(2个魔术方法 1个内置函数),相信对Python中属性的解析,相较于MRO,有…...

stm32—时钟、定时器和看门狗

1. 时钟 什么是时钟呢? 一个可以产生周期性信号的设备 什么是周期性信号? 1 ----- ----- ----- 0 ----- ----- ----- 所以时钟信号就是周期性变化的信号 关于时钟我们有两个比较重要…...

Windows平台RTSP|RTMP播放器如何实时调节音量

我们在做Windows平台RTSP、RTMP播放器的时候,有这样的技术需求,特别是多路监控的时候,并不是每一路audio都需要播放出来的,所以,这时候,需要有针对音量调节的设计: /** smart_player_sdk.cs* C…...

Leetcode JAVA刷刷站(10)正则表达式匹配

一、题目概述 二、思路方向 在Java中,实现一个支持.和*的正则表达式匹配器,可以通过递归或动态规划(DP)的方法来完成。这里,我将使用动态规划的方法来解决这个问题,因为它更容易理解和实现。 动态规划的思…...

合并图片为pdf

1.先使用IDM在网页下载: 2.按文件类型分组,在按名称大小排序,之后使用Acrobat合并文件成一个pdf即可...

【Linux Install】Ubuntu20, Windows10 双系统安装

1. 制作启动盘 1.1 下载 Ubuntu 系统镜像 ISO 文件 从 Ubuntu 官网下载 (https://cn.ubuntu.com/download/desktop)。官网访问慢的,从国内镜像点下。 1.2 烧录 Ubuntu ISO 镜像 下载 Rufus:从Rufus官网下载 Rufus 工具。 插入U 盘:将U盘插…...

Keepalived + LVS实现高可用

1、简介 LVS和Keepalived是Linux操作系统下实现高可用的负载均衡解决方案的重要工具。通过协同工作,它们能够实现一种高性能、高可用的负载均衡服务,使得用户能够透明地访问到集群中的服务。同时,它们还提供了强大的监控和故障切换功能&#…...

Gin框架接入Prometheus,grafana辅助pprof检测内存泄露

prometheus与grafana的安装 grom接入Prometheus,grafana-CSDN博客 Prometheus 动态加载 我们想给Prometheus新增监听任务新增ginapp项目只需要在原来的配置文件下面新增ginapp相关metric 在docker compose文件下面新增 执行 docker-compose up -d curl -X POST http://lo…...

上海凯泉泵业入职测评北森题库题型分析、备考题库、高分攻略

上海凯泉泵业(集团)有限公司是一家大型综合性泵业公司,专注于设计、生产、销售泵、给水设备及其控制设备。作为中国泵行业的领军企业,凯泉集团拥有7家企业和5个工业园区,总资产达到25亿元,生产性建筑面积35…...

Linux:基础IO

目录 1. stdin & stdout & stderr 2. 系统文件I/O 1. 接口介绍 open write read close lseek 2. open函数返回值 3. 文件描述符fd 0 & 1 & 2 文件描述符的分配规则 重回定向 dup2 简易Shell的模拟实现 4. FILE 5. 再谈对文件的理解 1. stdin …...

奥运奖牌窥视

1 前言 2024巴黎奥运会已经闭幕了,中国队创纪录地获得了海外举办的奥运会的最佳成绩,我们来个管中窥豹,看看中国队从哪些项目中取得了奖牌。 2 奖牌组成 游泳真是大项,小项数量众多,比如个人自由泳就有100m、200m、4…...