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

python-leetcode 55.子集

题目:

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

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


方法一:迭代法实现子集枚举

记原序列中元素的总数为 n,原序列中的每个数字 ai​ 的状态可能有两种,即「在子集中」和「不在子集中」。我们用 1 表示「在子集中」,0 表示不在子集中,,那么每一个子集可以对应一个长度为 n 的 0/1 序列,第 i 位表示 ai​ 是否在子集中。例如,n=3 ,a={5,2,9} 时:

可以发现 0/1 序列对应的二进制数正好从 0 到 2 n −1。我们可以枚举 mask∈[0,2 n −1],mask 的二进制表示是一个 0/1 序列,我们可以按照这个 0/1 序列在原集合当中取数。当我们枚举完所有 2 
n 个 mask,我们也就能构造出所有的子集。

class Solution(object):def subsets(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""ans=[] #一个空列表用于存储所有子集for i in range(1<<len(nums)):#位移操作,等价于 2 ** len(nums)subset=[]for j,x in enumerate(nums):# 遍历 nums,获取每个元素 x 及其索引 jif i>>j&1:# 如果 i 右移 j 位后与 1 按位与的结果为 1subset.append(x)# 将当前元素 x 添加到 subset 中ans.append(subset)return ans
  • 时间复杂度:O(n2n),其中 n 为 nums 的长度。
  • 空间复杂度:O(1)。返回值的空间不计

方法二:递归

开始假设输出子集为空,遍历数组,对于数组中的每一个整数,每一步都向输出子集中所有子集添加这个整数,并生成新的子集。

dfs(0)
├── 包含 nums[0] = 1
│   └── dfs(1)
│       ├── 包含 nums[1] = 2
│       │   └── dfs(2)
│       │       ├── 包含 nums[2] = 3
│       │       │   └── dfs(3) → 添加 [1, 2, 3]
│       │       └── 不包含 nums[2] = 3
│       │           └── dfs(3) → 添加 [1, 2]
│       └── 不包含 nums[1] = 2
│           └── dfs(2)
│               ├── 包含 nums[2] = 3
│               │   └── dfs(3) → 添加 [1, 3]
│               └── 不包含 nums[2] = 3
│                   └── dfs(3) → 添加 [1]
└── 不包含 nums[0] = 1
    └── dfs(1)
        ├── 包含 nums[1] = 2
        │   └── dfs(2)
        │       ├── 包含 nums[2] = 3
        │       │   └── dfs(3) → 添加 [2, 3]
        │       └── 不包含 nums[2] = 3
        │           └── dfs(3) → 添加 [2]
        └── 不包含 nums[1] = 2
            └── dfs(2)
                ├── 包含 nums[2] = 3
                │   └── dfs(3) → 添加 [3]
                └── 不包含 nums[2] = 3
                    └── dfs(3) → 添加 []

class Solution(object):def subsets(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""t=[]  #用于存储当前子集ans=[] # 用于存储所有子集def dfs(cur): #定义深度优先搜索函数,cur 表示当前处理的索引if cur==len(nums): ## 如果当前索引等于 nums 的长度,说明已经处理完所有元素ans.append(t[:])# # 将当前子集 t 的拷贝添加到结果 ans 中return t.append(nums[cur])#将当前元素 nums[cur] 添加到子集 t 中dfs(cur + 1)  # 递归处理下一个元素t.pop()# 回溯,移除当前元素,恢复子集 tdfs(cur+1)# 不包含当前元素,递归处理下一个元素dfs(0)return ans

时间复杂度:O(n×2**n )。一共 2 **n个状态,每种状态需要 O(n) 的时间来构造子集。

空间复杂度:O(n)。临时数组 t 的空间代价是 O(n),递归时栈空间的代价为 O(n)。

源自力扣官方题解
 

相关文章:

python-leetcode 55.子集

题目&#xff1a; 给定一个数组nums,数组中的元素互不相同&#xff0c;返回该数组所有可能子集&#xff08;幂集&#xff09; 解集不能包含重复的子集&#xff0c;可以按任意顺序返回解集 方法一&#xff1a;迭代法实现子集枚举 记原序列中元素的总数为 n&#xff0c;原序列…...

在LORA训练中,LORA模型的矩阵的行列是多少

在LORA训练中,LORA模型的矩阵的行列是多少: W n e w = W + α r B A W_{new}=W + \frac{\alpha}{r}BA...

冒泡排序:古老算法中的智慧启示

在计算机科学浩瀚的星空中&#xff0c;排序算法犹如璀璨的星辰&#xff0c;而冒泡排序恰似其中最朴实无华的一颗。这个诞生于计算机发展初期的经典算法&#xff0c;以其简单直观的逻辑原理&#xff0c;成为每个程序员启蒙阶段必经的试炼场。当我们凝视这个看似笨拙的排序方法时…...

基于ssm的电子病历系统(全套)

一、系统架构 前端&#xff1a;jsp | bootstrap | jquery 后端&#xff1a;spring | springmvc | mybatis 环境&#xff1a;jdk1.8 | mysql | maven | tomcat | idea 二、代码及数据库 三、功能介绍 01. 登录 02. 主页 03. 管理员-个人中心-修改密码…...

V2X验证

1. 标准和规范验证 欧洲对 DSRC 和 V2X 系统有一系列的标准和规范,主要由 ETSI (European Telecommunications Standards Institute) 和 IEEE 等组织制定。验证通常包括以下标准和规范: ETSI EN 302 571:这是DSRC在欧洲的主要标准,规定了DSRC系统的技术要求和操作条件。ET…...

SpringBoot美发门店管理系统开发与设计

在幽络源&#xff0c;我们致力于为开发者提供优质的技术资源和项目源码。今天&#xff0c;我们为大家分享一款基于SpringBoot开发的美发门店管理系统。该系统功能全面&#xff0c;操作便捷&#xff0c;适合中小型美发门店的管理需求。以下是系统的详细介绍。 系统功能模块 1.…...

Linux内核实时机制28 - RT调度器11 - RT 组调度

Linux内核实时机制28 - RT调度器11 - RT 组调度 相关数据结构 内核中通过static int sched_rt_runtime_exceeded(struct rt_rq *rt_rq)函数来判断实时任务运行时间是否超出带宽限制,判断这个运行队列rt_rq的运行时间是否超过了额定的运行时间。而“运行时间”和“额定时间”都…...

R语言——变量

参考资料&#xff1a;学习R 1、类 R中所有变量都有一个类&#xff0c;表明此变量属于什么类型。例如&#xff0c;大部分的数字是numeric类&#xff0c;逻辑值是logical类。其实&#xff0c;因为R没有标量类型&#xff08;scalar type&#xff09;&#xff0c;所以更严格地我说…...

Appium使用文档

Appium旨在支持许多不同平台&#xff08;移动端、网页端、桌面端等&#xff09;的UI自动化。不仅如此&#xff0c;它还旨在支持用不同语言&#xff08;JS、Java、Python等&#xff09;编写的自动化代码。 Appium移动端自动化要求如下&#xff1a; 安装Appium安装UiAutomator2…...

Houdini :《哪吒2》神话与科技碰撞的创新之旅

《哪吒2》&#xff08;即《哪吒之魔童闹海》&#xff09;截止至今日&#xff0c;荣登全球票房榜第五。根据猫眼专业版数据&#xff0c;截至2025年3月15日&#xff0c;《哪吒2》全球累计票房&#xff08;含预售及海外&#xff09;超过150.19亿元&#xff0c;超越《星球大战&…...

单台openEuler24.03 LTS下的开源大数据环境搭建

目录 概述 准备 虚拟机基本设置 关闭及禁用防火墙 修改主机名 静态ip 映射主机名 创建普通用户 SSH免密登录 目录准备 安装Java 下载Java 解压 设置环境变量 安装Hadoop 下载hadoop 解压 设置环境变量 查看版本 配置hadoop 配置hadoop_env.sh 配置core-s…...

HarmonyOS开发,深拷贝、浅拷贝的封装和调用

在 HarmonyOS 开发中&#xff0c;实现深拷贝和浅拷贝可以通过封装工具类来完成。下面分别介绍浅拷贝和深拷贝的实现方式&#xff0c;并将它们封装成一个工具类。 浅拷贝和深拷贝的区别 浅拷贝&#xff1a;创建一个新对象&#xff0c;新对象的属性引用原始对象的属性。也就是说…...

C 环境设置指南

C 环境设置指南 引言 C语言作为一种历史悠久且功能强大的编程语言,在软件开发和系统编程领域占有举足轻重的地位。C语言环境设置是进行C语言编程的第一步,也是确保编程顺利进行的关键。本文将详细介绍C语言环境的设置过程,包括系统要求、开发工具的选择、环境变量的配置等…...

2018年全国职业院校技能大赛高职组-计算机网络应用竞赛竞赛样题E卷

目录 总体规划 模块二:设备基础信息配置 模块三:网络搭建与网络冗余备份方案部署 模块四:移动互联网搭建与网优 模块五:出口安全防护与远程接入 总体规划 医院在进行网络部分信息化建设方案设计过程中,需要保证医院、血液中心通过社保网进行互连互通,同时满足献血中心与医…...

大华HTTP协议在智联视频超融合平台中的接入方法

一. 大华HTTP协议介绍 大华HTTP协议是大华股份&#xff08;Dahua Technology&#xff09;为其安防监控设备开发的一套基于HTTP/HTTPS的通信协议&#xff0c;主要用于设备与客户端&#xff08;如PC、手机、服务器&#xff09;之间的数据交互。该协议支持设备管理、视频流获取、…...

Dify Docker 私有化部署遇到的问题

Dify 版本为1.01&#xff0c;本地使用 docker desktop&#xff0c;版本为4.38.0 (181591)&#xff0c;以下是Dify部署及使用过程中遇到的问题&#xff0c;后续持续更新... db无法启动&#xff0c;一直提示&#xff1a;Permissions should be urwx (0700) or urwx,grx (0750).具…...

Python学习第十九天

Django-分页 后端分页 Django提供了Paginator类来实现后端分页。Paginator类可以将一个查询集&#xff08;QuerySet&#xff09;分成多个页面&#xff0c;每个页面包含指定数量的对象。 from django.shortcuts import render, redirect, get_object_or_404 from .models impo…...

大数据技术链路详解

随着大数据技术的不断发展&#xff0c;各种新兴技术层出不穷&#xff0c;今天我们就来详细拆解一条完整的大数据链路&#xff0c;看看每个环节都有哪些最新技术参与&#xff0c;以及它们如何发挥作用。 一、数据采集层 在大数据处理的第一步&#xff0c;数据采集至关重要。现代…...

vue computed 计算属性简述

Vue 的 ‌计算属性&#xff08;Computed Properties&#xff09;‌ 是 Vue 实例中一种特殊的属性&#xff0c;用于‌声明式地定义依赖其他数据动态计算得出的值‌。它的核心优势在于能够自动追踪依赖关系&#xff0c;并缓存计算结果&#xff0c;避免重复计算&#xff0c;提升性…...

365天之第P10周:Pytorch实现车牌识别

365天之第P10周&#xff1a;Pytorch实现车牌识别 Pytorch实现车牌识别 365天之第P10周&#xff1a;Pytorch实现车牌识别一、导入数据1.获取类别名2. 数据可视化3. 标签数字化4. 加载数据文件5. 划分数据 二、自建模型三、 训练模型1. 优化器与损失函数2. 模型训练 四、 结果分析…...

【Docker】-Docker Compose+Dockerfile最佳实践

最佳实践 在实际生产环境中&#xff0c;Docker Compose Dockerfile 的最佳实践通常包括以下几部分&#xff1a; 使用 Dockerfile 构建微服务镜像使用 docker-compose.yml 管理多个微服务使用 volumes 进行数据持久化使用 networks 进行服务间通信使用 depends_on 确保依赖服…...

TSB - AD 解读 — 迈向可靠、透明的 TSAD 任务

目录 一 文章动机 二 TSAD 领域内的两类缺陷 三 数据集的构建 四 实验结果及结论 项目宣传链接&#xff1a;TSB-AD 代码链接&#xff1a; TheDatumOrg/TSB-AD: TSB-AD: Towards A Reliable Time-Series Anomaly Detection Benchmark 原作者解读&#xff1a;NeurIPS 2…...

Linux 入门:权限的认识和学习

目录 一.shell命令以及运行原理 二.Linux权限的概念 1.Linux下两种用户 cannot open directory .: Permission denied 问题 2.Linux权限管理 1).是什么 2).为什么&#xff08;权限角色目标权限属性&#xff09; 3).文件访问者的分类&#xff08;角色&#xff09; 4).文…...

多任务学习与持续学习微调:深入探索大型语言模型的性能与适应性

引言 大型语言模型&#xff08;LLMs&#xff09;的出现极大地推动了自然语言处理领域的发展。为了使其在各种特定任务和动态环境中表现出色&#xff0c;微调技术至关重要。本节将深入探讨多任务学习&#xff08;Multi-task Learning, MTL&#xff09;和持续学习&#xff08;Co…...

Cocos Creator Shader入门实战(四):预处理宏定义和Chunk

引擎&#xff1a; 3.8.5 您好&#xff0c;我是鹤九日&#xff01; 回顾 学习Shader&#xff0c;前期是让人烦躁无味的&#xff0c;后期可能就是各种的逻辑让人抓耳挠腮。 一成不变的内容&#xff1a;遵循引擎设定的规则&#xff0c;理解引擎要求的规范。 这里&#xff0c;简单…...

[蓝桥杯 2023 省 B] 飞机降落

[蓝桥杯 2023 省 B] 飞机降落 题目描述 N N N 架飞机准备降落到某个只有一条跑道的机场。其中第 i i i 架飞机在 T i T_{i} Ti​ 时刻到达机场上空&#xff0c;到达时它的剩余油料还可以继续盘旋 D i D_{i} Di​ 个单位时间&#xff0c;即它最早可以于 T i T_{i} Ti​ 时刻…...

STAR Decomposition 一种针对极端事件的信号分解方法 论文精读加复现

STAR 分解&#x1f680; 在时序预测任务中&#xff0c;为了情绪化信号的各种成分&#xff0c;例如趋势信息季节信息等往往都需要对信号进行分解。目前熟知的分解方式有很多种&#xff0c;经验模态分解 EMD 变分模态分解 VMD &#xff0c;还有 集合经验模态分解 EEMD&#xff0c…...

matlab中如何集成使用python

在 MATLAB 中集成使用 Python 可以通过调用 Python 脚本或函数来实现。MATLAB 提供了 py 模块来直接调用 Python 代码。以下是一个简单的示例&#xff0c;展示如何在 MATLAB 中调用 Python 函数。 示例&#xff1a;在 MATLAB 中调用 Python 函数 1. 编写 Python 函数 首先&a…...

使用matlab求伴随矩阵

已知三阶方阵&#xff1a; 计算行列式det 计算逆矩阵inv 如何det不等于0&#xff0c;伴随矩阵 行列式det*逆矩阵inv >> A[1 0 0;1 1 -1;-2 0 3]A 1 0 01 1 -1-2 0 3>> det(A)ans 3>> >> A_invinv(A)A_inv 1.0000 …...

音视频处理的“瑞士军刀”与“积木”:FFmpeg 与 GStreamer 的深度揭秘

一、发展历史与生态演进对比 FFmpeg的成长轨迹 诞生背景&#xff1a;2000年由Fabrice Bellard创建&#xff0c;最初为解决视频编码标准化问题而生。早期版本仅支持MPEG-1编码&#xff0c;但凭借开源社区协作&#xff0c;迅速扩展为全格式编解码工具。技术扩张&#xff1a;2004年…...

Debezium日常分享系列之:Debezium 3.1.0.Beta1发布

Debezium日常分享系列之&#xff1a;Debezium 3.1.0.Beta1发布 新特性和改进Debezium 平台的首次发布Percona 的最小锁定新的 Oracle 源信息 SCN 和时间戳字段Vitess Epoch/零日期列解析的变化Vitess 二进制排序的 tiny、medium 和 long 文本列的变化CloudEvent traceparent 支…...

智能汽车图像及视频处理方案,支持视频智能剪辑能力

在智能科技日新月异的今天&#xff0c;汽车已不仅仅是代步工具&#xff0c;它们正逐步进化为集出行、娱乐、生活于一体的智能移动空间。在这场汽车行业的智能化变革中&#xff0c;美摄科技以其卓越的智能汽车图像及视频处理方案&#xff0c;引领了一场前所未有的视觉盛宴&#…...

《从零手写Linux Shell:详解进程控制、环境变量与内建命令实现 --- 持续更新》

承接上文Linux 进程的创建、终止、等待与程序替换保姆级讲解-CSDN博客&#xff0c;涉及所用到的代码&#xff0c;本文所绑定的资源就是上篇文章的主要代码。 完整代码在文章末尾 目录 1.实现编写代码输出一个命令行 a.如何获取自己的用户名&#xff0c;主机名&#xff0c;路径…...

postgresql 高版本pgsql备份在低版本pgsql中恢复失败,报错:“unsupported version”

关键字 PostgreSQL、pg_restore、版本兼容性、数据库迁移、pg_dump、备份恢复、unsupported version in file header 背景环境 系统配置 环境类型操作系统PostgreSQL版本内存工具链测试环境Windows 111616GBNavicat/PgAdmin生产环境Windows Server 2012 R2128GBPgAdmin/命令…...

裸机开发-GPIO外设

重新开始学ZYNQ开发&#xff0c;学完上linux系统 基础知识&#xff1a;ZYNQ 的三种GPIO &#xff1a;MIO、EMIO、AXI - FPGA/ASIC技术 - 电子发烧友网 GPIO是ZYNQ PS端的一个IO外设&#xff0c;用于观测&#xff08;input&#xff09;和控制&#xff08;output&#xff09;器…...

STM32——独立看门狗(IWDG)

IWDG 简介 独立看门狗本质上是一个 定时器 &#xff0c;这个定时器有一个输出端&#xff0c;可以输出复位信号。该定时器是一个 12 位的递减计数器 &#xff0c;当计数器的值减到 0 的时候&#xff0c;就会产生一个复位信号。如果 在计 数没减到 0 之前&#xff0c;重置计…...

使用STM32CubeMX+DMA+空闲中断实现串口接收和发送数据(STM32G070CBT6)

1.STM32CubeMX配置 &#xff08;1&#xff09;配置SYS &#xff08;2&#xff09;配置RCC &#xff08;3&#xff09;配置串口&#xff0c;此处我用的是串口4&#xff0c;其他串口也是一样的 &#xff08;4&#xff09;配置DMA&#xff0c;将串口4的TX和RX添加到DMA中 &#…...

连续出现的字符(信息学奥赛一本通-1148)

【题目描述】 给定一个字符串&#xff0c;在字符串中找到第一个连续出现至少k次的字符。 【输入】 第一行包含一个正整数k&#xff0c;表示至少需要连续出现的次数。1 ≤ k ≤ 1000。 第二行包含需要查找的字符串。字符串长度在1到2500之间&#xff0c;且不包含任何空白符。 【…...

matlab 正态分布

目录 一、概述1、参数2、概率密度函数3、累积分布函数二、代码案例1、拟合正态分布对象2、估计参数3、计算并绘制正态分布的概率密度函数4、绘制标准正态分布的正态累积分布函数5、比较 gamma 和正态分布的概率密度函数6、正态分布和对数正态分布之间的关系7、比较 Student t 和…...

C# MVC项目部署II后错误,403禁止访问:访问被拒绝问题处理

C# MVC项目部署II后错误&#xff0c;403禁止访问&#xff1a;访问被拒绝问题处理 问题如下&#xff1a; 解决办法&#xff1a; 1. 应用程序池要选v4.xx&#xff0c;托管模式选“集成” 2. 把asp.net 4.xx安装在iis上&#xff0c;方法&#xff1a; cd \Windows\Microsoft .NE…...

有趣的算法实践:整数反转与回文检测(Java实现)

题目描述&#xff1a;整数反转与回文检测 要求实现两个功能&#xff1a; 将输入的整数反转&#xff08;保留符号&#xff0c;如输入-123返回-321&#xff09;判断反转后的数是否为回文数&#xff08;正反读相同&#xff09; 示例&#xff1a; 输入&#xff1a;123 → 反转结…...

数学建模:MATLAB循环神经网络

一、简述 1.循环神经网络 循环神经网络&#xff08;RNN&#xff09;是一种用于处理序列数据的神经网络。不同于传统的前馈神经网络&#xff0c;RNN在隐藏层中加入了自反馈连接&#xff0c;使得网络能够对序列中的每个元素执行相同的操作&#xff0c;同时保持一个“记忆”状态…...

东隆科技携手PRIMES成立中国校准实验室,开启激光诊断高精度新时代

3月12日&#xff0c;上海慕尼黑光博会期间&#xff0c;东隆科技正式宣布与德国PRIMES共同成立“中国校准实验室”。这一重要合作标志着东隆科技在本地化服务领域的优势与PRIMES在激光光束诊断领域的顶尖技术深度融合&#xff0c;旨在为中国客户提供更快速、更高精度的服务以及本…...

【MySQL】B树和B+树的区别?MySQL为什么选用B+树作为索引数据结构?

B树和B树的区别&#xff1a; 结构方面&#xff1a; 1.节点存储内容&#xff1a; B树&#xff1a; 节点同时存储索引和数据。B树&#xff1a;只有叶子节点存储数据记录或指向数据记录的指针&#xff0c;非叶子节点只存键值&#xff0c;用于索引。 B 树的非叶子节点可以存储更…...

使用yolov8+flask实现精美登录界面+图片视频摄像头检测系统

这个是使用flask实现好看登录界面和友好的检测界面实现yolov8推理和展示&#xff0c;代码仅仅有2个html文件和一个python文件&#xff0c;真正做到了用最简洁的代码实现复杂功能。 测试通过环境&#xff1a; windows x64 anaconda3python3.8 ultralytics8.3.81 flask1.1.2…...

Cursor的使用感受,帮你使用好自动化编程工具,整理笔记

使用感受 说实话&#xff0c;我觉得cursor还是好用的&#xff0c;可能我刚开始使用&#xff0c;没有使用的非常的熟练&#xff0c;运用也没有非常的透彻&#xff0c;总体体验还是不错的&#xff0c;在使用它时&#xff0c;我优先考虑&#xff0c;前端页面功能复用的时候&#…...

2024浙江大学计算机考研上机真题

2024浙江大学计算机考研上机真题 2024浙江大学计算机考研复试上机真题 2024浙江大学计算机考研机试真题 2024浙江大学计算机考研复试机试真题 历年浙江大学计算机复试上机真题 历年浙江大学计算机复试机试真题 2024浙江大学计算机复试上机真题 2024浙江大学计算机复试机试真题 …...

JS逆向:通达OA Office Anywhere 2019 的前端密码加密逆向分析,并使用Python构建通达OA登录

免责声明 本文仅为技术研究与渗透测试思路分享,旨在帮助安全从业人员更好地理解相关技术原理和防御措施。任何个人或组织不得利用本文内容从事非法活动或攻击他人系统。 如果任何人因违反法律法规或不当使用本文内容而导致任何法律后果,本文作者概不负责。 请务必遵守法律…...

贴吧ip什么意思?贴吧ip可以查到姓名吗

贴吧作为百度旗下的一个重要社区平台&#xff0c;一直以来都吸引着大量用户进行交流和讨论。然而&#xff0c;随着网络环境的日益复杂&#xff0c;用户的隐私保护问题也日益凸显。其中&#xff0c;贴吧IP地址的显示及其与个人信息的关系&#xff0c;成为不少用户关注的焦点。本…...

【css酷炫效果】纯CSS实现进度条加载动画

【css酷炫效果】纯CSS实现进度条加载动画 缘创作背景html结构css样式完整代码基础版进阶版 效果图 通过CSS渐变与背景位移动画&#xff0c;无需JavaScript即可创建流体动态进度条。 想直接拿走的老板&#xff0c;链接放在这里&#xff1a;https://download.csdn.net/download/u…...