LeetCode 0090.子集 II:二进制枚举 / 回溯
【LetMeFly】90.子集 II:二进制枚举 / 回溯
力扣题目链接:https://leetcode.cn/problems/subsets-ii/
给你一个整数数组 nums
,其中可能包含重复元素,请你返回该数组所有可能的 子集(幂集)。
解集 不能 包含重复的子集。返回的解集中,子集可以按 任意顺序 排列。
示例 1:
输入:nums = [1,2,2] 输出:[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2:
输入:nums = [0] 输出:[[],[0]]
提示:
1 <= nums.length <= 10
-10 <= nums[i] <= 10
解题方法一:位运算(二进制枚举)
使用变量 s t a t e state state从 0 0 0枚举到 2 n − 1 2 ^ n - 1 2n−1,其中 s t a t e state state二进制下的每一位代表选择 n u m s [ i ] nums[i] nums[i]或不选。
枚举之前先将 n u m s nums nums排序,若当前选择方案不存在则加入答案数组中。
- 时间复杂度 O ( n log n + n 2 × 2 n ) O(n\log n + n^2\times2^n) O(nlogn+n2×2n),其中 n = l e n ( n u m s ) n=len(nums) n=len(nums)
- 空间复杂度 O ( n ) O(n) O(n),返回值不计入
AC代码
C++
/** @Author: LetMeFly* @Date: 2025-02-05 12:22:09* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-02-05 12:24:34*/
class Solution {
public:vector<vector<int>> subsetsWithDup(vector<int>& nums) {sort(nums.begin(), nums.end());vector<vector<int>> ans;for (int i = 0; i < (1 << nums.size()); i++) {vector<int> thisAns;for (int j = 0; j < nums.size(); j++) {if (i >> j & 1) {thisAns.push_back(nums[j]);}}if (find(ans.begin(), ans.end(), thisAns) == ans.end()) {ans.push_back(thisAns);}}return ans;}
};
解题方法二:回溯
类似LeetCode 40.组合总和 II:回溯 + 剪枝,写一个dfs
函数枚举选与不选两种情况。
- 如果当前下标已越界,则将当前方案添加到答案数组中
- 选当前元素时,将当前元素加入当前方案,递归,再将当前元素移除当前方案(回溯)
- 不选当前元素时,如果下一个元素(下下个元素,…)和当前元素一样,那么也不能选。
以上。
- 时间复杂度 O ( n × 2 n ) O(n^\times2^n) O(n×2n),其中 n = l e n ( n u m s ) n=len(nums) n=len(nums)
- 空间复杂度 O ( n ) O(n) O(n),返回值不计入
AC代码
C++
/** @Author: LetMeFly* @Date: 2025-02-05 12:25:14* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-02-05 12:28:24*/
class Solution {
private:vector<vector<int>> ans;vector<int> now;void dfs(vector<int>& a, int loc) {if (loc == a.size()) {ans.push_back(now);return;}// 选当前now.push_back(a[loc]);dfs(a, loc + 1);now.pop_back();// 不选当前int next = loc + 1;while (next < a.size() && a[loc] == a[next]) {next++;}dfs(a, next);}
public:vector<vector<int>> subsetsWithDup(vector<int>& nums) {sort(nums.begin(), nums.end());dfs(nums, 0);return ans;}
};
Python
'''
Author: LetMeFly
Date: 2025-02-05 12:29:11
LastEditors: LetMeFly.xyz
LastEditTime: 2025-02-05 12:32:04
'''
from typing import Listclass Solution:def dfs(self, loc: int) -> None:if loc == len(self.a):self.ans.append([i for i in self.now])return# 选当前self.now.append(self.a[loc])self.dfs(loc + 1)self.now.pop()# 不选当前next = loc + 1while next < len(self.a) and self.a[next] == self.a[loc]:next += 1self.dfs(next)def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:self.ans: List[List[int]] = []self.a = sorted(nums)self.now = []self.dfs(0)return self.ans
Java
/** @Author: LetMeFly* @Date: 2025-02-05 12:29:23* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-02-05 12:38:09*/
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;class Solution {private List<List<Integer>> ans = new ArrayList<>();private List<Integer> now = new ArrayList<>();private int[] a;private void dfs(int loc) {if (loc == a.length) {ans.add(new ArrayList<>(now));return;}// 选当前now.add(a[loc]);dfs(loc + 1);now.remove(now.size() - 1);// 不选int next = loc + 1;while (next < a.length && a[next] == a[loc]) {next++;}dfs(next);}public List<List<Integer>> subsetsWithDup(int[] nums) {Arrays.sort(nums);a = nums;dfs(0);return ans;}
}
Go
/** @Author: LetMeFly* @Date: 2025-02-05 12:29:25* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-02-05 12:42:51*/
package mainimport "sort"var (ans [][]intnow,a []int
)func dfs_S2(loc int) {if loc == len(a) {ans = append(ans, append([]int{}, now...))return}// 选now = append(now, a[loc])dfs_S2(loc + 1)now = now[:len(now) - 1]// 不选next := loc + 1for next < len(a) && a[next] == a[loc] {next++}dfs_S2(next)
}func subsetsWithDup(nums []int) [][]int {ans = make([][]int, 0)now = make([]int, 0)sort.Ints(nums)a = numsdfs_S2(0)return ans
}
同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/145453136
相关文章:
LeetCode 0090.子集 II:二进制枚举 / 回溯
【LetMeFly】90.子集 II:二进制枚举 / 回溯 力扣题目链接:https://leetcode.cn/problems/subsets-ii/ 给你一个整数数组 nums ,其中可能包含重复元素,请你返回该数组所有可能的 子集(幂集)。 解集 不能 …...
Pytest+selenium UI自动化测试实战实例
今天来说说pytest吧,经过几周的时间学习,有收获也有疑惑,总之最后还是搞个小项目出来证明自己的努力不没有白费。 环境准备 1 确保您已经安装了python3.x 2 配置python3pycharmselenium2开发环境 3 安装pytest库pip install p…...
黑马点评 - 商铺类型缓存练习题(Redis List实现)
首先明确返回值是一个 List<ShopType> 类型那么我们修改此函数并在 TypeService 中声明 queryTypeList 方法,并在其实现类中实现此方法 GetMapping("list")public Result queryTypeList() {return typeService.queryTypeList();}实现此方法首先需要…...
C++ 创建和配置dll与lib库
C简明教程(13)创建和配置dll与lib库_怎样生成lib库和dll库-CSDN博客 C 动态库与静态库详解 一、为什么要引入库的概念 在 C 编程中,随着项目规模的不断扩大,代码量也会急剧增加。如果将所有代码都写在一个源文件中,…...
深度剖析 Veo2 工具:解锁 AI 视频创作新境界
在当下这个 AI 技术日新月异的时代,各种 AI 工具如雨后春笋般涌现,让人目不暇接。今天,我就来给大家好好说道说道谷歌旗下的 Veo2,这可是一款在 AI 视频创作领域相当有分量的工具。好多朋友都在问,Veo2 到底厉害在哪?好不好上手?能在哪些地方派上用场?别着急,今天我就…...
LabVIEW自定义测量参数怎么设置?
以下通过一个温度采集案例,说明在 LabVIEW 中设置自定义测量参数的具体方法: 案例背景 假设使用 NI USB-6009 数据采集卡 和 热电偶传感器 监测温度,需自定义以下参数: 采样率:1 kHz 输入量程:0~10 V&a…...
JVM执行流程与架构(对应不同版本JDK)
直接上图(对应JDK8以及以后的HotSpot) 这里主要区分说明一下 方法区于 字符串常量池 的位置更迭: 方法区 JDK7 以及之前的版本将方法区存放在堆区域中的 永久代空间,堆的大小由虚拟机参数来控制。 JDK8 以及之后的版本将方法…...
数据治理项目为什么沦为了PPT工程?
数据治理项目为什么沦为了PPT工程? 数据治理项目为什么沦为PPT工程数据治理项目面临的深层挑战数据治理项目的破局之道 "这个项目明明做了快一年了,怎么感觉还在原地踏步?"数据治理小张最近很烦恼。 整天泡在会议室里,写…...
module ‘matplotlib.cm‘ has no attribute ‘get_cmap‘
目录 解决方法1: 解决方法2,新版api改了: module matplotlib.cm has no attribute get_cmap 报错代码: cmap matplotlib.cm.get_cmap(Oranges) 解决方法1: pip install matplotlib3.7.3 解决方法2,新版…...
HTML5 教程之标签(3)
HTML5 <center> 标签 (已废弃) 定义和用法 <center> 标签对其包围的文本进行水平居中处理。HTML5不支持使用<center>标签,因此有关该标签的更多信息,请参考“HTML <center>标签”部分! 示例: <center>这个…...
告别传统办公软件,这款编辑器让你事半功倍!
文章目录 1 界面的多样性2 性能优化3 文档编辑器的新功能4 外部文本支持5 体验感想 ONLYOFFICE最近发布了文档8.2版本,带来了众多新特性和性能改进。作为一名用户和开发者,我对这些更新进行了深入的体验,感受到了不少亮点。 新版本特别强调了…...
AI协助探索AI新构型自动化创新的技术实现
一、AI自进化架构的核心范式 1. 元代码生成与模块化重构 - 代码级自编程:基于神经架构搜索的强化学习框架,AI可通过生成元代码模板(框架的抽象层定义、神经元结点-网络拓扑态的编码抽象定义)自动组合功能模块。例如࿰…...
全能型免费内网穿透工具,全面支持macOS、Windows、Linux及Docker系统
1. 登陆官网网址并注册帐号 ngrok | API Gateway, Kubernetes Networking Secure Tunnels 2 下载并安装工具 3. 启动工具 在命令行执行 ngrok http http://localhost:8080 其中端口可换成用户自己想要穿透的端口 4. 获取穿透地址 命令执行后会出现如下画面,红…...
Web - CSS3浮动定位与背景样式
概述 这篇文章主要介绍了 CSS3 中的浮动定位、背景样式、变形效果等内容。包括 BFC 规范与创建方法、浮动的功能与使用要点、定位的多种方式及特点、边框与圆角的设置、背景的颜色、图片等属性、多种变形效果及 3D 旋转等,还提到了浏览器私有前缀。 BFC规范与浏览…...
VUE之组件通信(二)
1、v-model v-model的底层原理:是:value值和input事件的结合 $event到底是啥?啥时候能.target 对于原生事件,$event就是事件对象 ,能.target对应自定义事件,$event就是触发事件时,所传递的数据ÿ…...
Gauss高斯:建表语法,存储方式,OLTP和OLAP,系统时间,数组,分组(grouping set,rollup)
数据库和表的语法 数据库 表 oracle,高斯, hive的默认存储方式都是列式存储 存储方式 高斯数据库(GaussDB)支持列式存储和行式存储 OLTP 与 OLAP OLTP(联机事务处理,Online Transaction Processing)是一种用于管理…...
Java基础进阶
Java基础进阶 异常 概述 异常就是程序出现了不正常的情况 具体分为:Throwable—>(Error Exception);Exception—>(RuntimeException 非RuntimeException) Throwable类是Java语言中所有错误和异常的祖宗类;(上面还有Object类) Thr…...
【数据结构】链表应用1
链表应用 面试题 02.02.返回倒数第k个节点题目描述思路解题过程复杂度 查找相同后缀题目描述解题思路完整代码: 删除绝对值相等的节点题目描述解题思路代码 面试题 02.02.返回倒数第k个节点 题目描述 实现一种算法,找出单向链表中倒数第 k 个节点。返回…...
python gltf生成预览图
使用Python生成GLTF模型的预览图 随着3D技术的不断发展,GLTF(GL Transmission Format)逐渐成为了Web和移动应用程序中最流行的3D文件格式之一。GLTF文件不仅能以较小的体积存储复杂的3D模型,还支持动画、材质、光照和纹理等特性。…...
HTTP和HTTPS协议详解
HTTP和HTTPS协议详解 HTTP详解什么是http协议http协议的发展史http0.9http1.0http1.1http2.0 http协议的格式URI和URL请求request响应response http协议完整的请求与响应流程 HTTPS详解为什么使用HTTPSSSL协议HTTPS通信过程TLS协议 HTTP详解 什么是http协议 1、全称Hyper Tex…...
实战:利用百度站长平台加速网站收录
本文转自:百万收录网 原文链接:https://www.baiwanshoulu.com/33.html 利用百度站长平台加速网站收录是一个实战性很强的过程,以下是一些具体的步骤和策略: 一、了解百度站长平台 百度站长平台是百度为网站管理员提供的一系列工…...
专门记录台式电脑常见问题
1、蓝屏死机,检查内存硬盘和cpu 2、拆内存条,用橡皮擦金手指 3、放主板静电,扣主板电池 4、系统时间不正确,主板电池没电 5、开机键坏了 6、电脑主机的风扇转,正常通电运行,但显示器没信号。看键盘的num键&…...
数据库系统概念第六版记录 一
1.关系型数据库 关系型数据库(Relational Database,简称 RDB)是基于关系模型的一种数据库,它通过表格的形式来组织和存储数据。每个表由若干行(记录)和列(字段)组成,数据…...
本地Ollama部署DeepSeek R1模型接入Word
目录 1.本地部署DeepSeek-R1模型 2.接入Word 3.效果演示 4.问题反馈 上一篇文章办公新利器:DeepSeekWord,让你的工作更高效-CSDN博客https://blog.csdn.net/qq_63708623/article/details/145418457?spm1001.2014.3001.5501https://blog.csdn.net/qq…...
Meta Sapiens AI论文解读:人类视觉模型基石初现,AI 未来走向何方?
一、引言 在本文中,我们将深入探讨 Meta AI 的一项新成果,该成果发表于一篇题为《Sapiens:人类视觉模型的基础》的研究论文中。这篇论文介绍了一系列模型,这些模型针对四项以人类为中心的基本任务,正如我们在上面的演示…...
输入类控件和多元素控件【QT】
文章目录 输入类控件QLineEdit Text EditCombo BoxSpin BoxDialSlider多元素控件QListWidget TableWidetTreeWidgetQGroupBoxTab Widget# QVBoxLayout# QHBoxLayoutQGridLayoutQFormLayout 输入类控件 QLineEdit 例如: 实现一个用户输入姓名 密码 电话 性别 的功能…...
一键开启/关闭deepseek
一键开启/关闭 Deepseek对应下载的模型一键开启 Deepseek,一键关闭Deepseek双击对应的bat,就可以启动https://mbd.pub/o/bread/Z56YmpZvbat 下载:https://mbd.pub/o/bread/Z56YmpZv 可以自己写下来,保存成bat文件,也可…...
gitea - fatal: Authentication failed
文章目录 gitea - fatal: Authentication failed概述run_gitea_on_my_pkm.bat 笔记删除windows凭证管理器中对应的url认证凭证启动gitea服务端的命令行正常用 TortoiseGit 提交代码备注END gitea - fatal: Authentication failed 概述 本地的git归档服务端使用gitea. 原来的用…...
Spring AI 智能体通过 MCP 集成本地文件数据
作者:刘军 Model Context Protocol(MCP)简介 模型上下文协议(即 Model Context Protocol,MCP) [ 1] 是一个开放协议,它规范了应用程序如何向大型语言模型(LLM)提供上下…...
音视频入门基础:RTP专题(5)——FFmpeg源码中,解析SDP的实现
一、引言 FFmpeg源码中通过ff_sdp_parse函数解析SDP。该函数定义在libavformat/rtsp.c中: int ff_sdp_parse(AVFormatContext *s, const char *content) {const char *p;int letter, i;char buf[SDP_MAX_SIZE], *q;SDPParseState sdp_parse_state { { 0 } }, *s1…...
MyBatis XML文件配置
目录 一、 配置连接字符串和MyBatis 二、书写持久层代码 2.1 添加Mapper接口 2.2 添加UserlnfoXMLMapper.xml 三、增删改查 3.1 、增(Insert) 3.2、删(Delete) 3.3、改 (Update) 3.4、查 (Select) MyBatisXML的方式需要以下两步&am…...
【Leetcode 热题 100】1143. 最长公共子序列
问题背景 给定两个字符串 t e x t 1 text_1 text1 和 t e x t 2 text_2 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 0 0。 一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变…...
【算法】动态规划专题④ ——LCS(最长公共子序列)+ LPS(最长回文子序列) python
目录 前置知识LCS举一反三LPS 前置知识 【算法】动态规划专题③ ——二维DP python 子序列定义为: 不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。 LCS 最长公共子序列 https://www.lanqiao.cn/problems/1189/learning/?p…...
Cesium点集中获取点的id,使用viewer.value.entities.getById报错的解决方法
错误代码: viewer.value.entities.getById(pickedObject.id) 报错: 可以正常获取movement.position但是一直出现如下报错,无法获得航点的id,通过断点定位为 viewer.value.entities.getById(pickedObject.id)导致的报错 解决方…...
360手机刷机 360手机解Bootloader 360手机ROOT
360手机刷机 360手机解Bootloader 360手机ROOT 问:360手机已停产,现在和以后,能刷机吗? 答:360手机,是肯定能刷机的 360手机资源下载网站 360手机-360手机刷机RootTwrp 360os.top 360rom.github.io 一、…...
深度探索DeepSeek-R1:AI大模型的本地应用与个人知识库构建
深度探索DeepSeek-R1:AI大模型的本地应用与个人知识库构建 引言 在当今这个信息爆炸的时代,如何高效地存储、处理和获取知识,已经成为每个人面临的挑战。想象一下,如果你能在没有互联网连接的情况下,构建一个属于自己…...
LabVIEW图像采集与应变场测量系统
开发了一种基于LabVIEW的图像采集与应变场测量系统,提供一种高精度、非接触式的测量技术,用于监测物体的全场位移和应变。系统整合了实时监控、数据记录和自动对焦等功能,适用于工程应用和科学研究。 项目背景 传统的位移和应变测量技术往往…...
解决DeepSeek服务器繁忙问题:本地部署与优化方案
deepseek服务器崩了,手把手教你如何在手机端部署一个VIP通道! 引言 随着人工智能技术的快速发展,DeepSeek等大语言模型的应用越来越广泛。然而,许多用户在使用过程中遇到了服务器繁忙、响应缓慢等问题。本文将探讨如何通过本地部…...
今日AI和商界事件(2025-02-05)
今日AI领域的相关事件主要包括以下几个方面: 一、DeepSeek引发全球关注 性能与成本优势: DeepSeek推出的R1模型性能出色,成本较低,在全球AI行业引发震动。该模型在数学、代码处理等方面性能优异,受到广泛赞誉。 平台…...
SQL 秒变 ER 图 sql转er图
🚀SQL 秒变 ER 图,校园小助手神了! 学数据库的宝子们集合🙋♀️ 是不是每次碰到 SQL 转 ER 图就头皮发麻?看着密密麻麻的代码,脑子直接死机,好不容易理清一点头绪,又被复杂的表关…...
SQL server 创建DB Link 详解
在日常工作中,经常涉及到跨库操作,为使跨数据库的操作变得更加灵活高效,我们可以在 SQL Server 中建立数据库链接( DB Link),实现 SQL Server 数据库与其他数据库(如 Oracle, MySQL 等ÿ…...
25.2.5学习记录
今天主要学的是哈希表的理论知识,但是都是c实现,C语言的代码实现还没有完全搞明白。 在写题的时候,懵懂的学着正确代码,用C语言模拟实现哈希表去解题。 在哈希表的理论知识中,学到哈希函数,了解哈希冲突产…...
C# List 列表综合运用实例⁓Hypak原始数据处理编程小结
C# List 列表综合运用实例⁓Hypak原始数据处理编程小结 1、一个数组解决很麻烦引出的问题1.1、RAW 文件尾部数据如下:1.2、自定义标头 ADD 或 DEL 的数据结构如下: 2、程序 C# 源代码的编写和剖析2.1、使用 ref 关键字,通过引用将参数传递,以…...
不可信的搜索路径(CWE-426)
漏洞描述:程序使用关键资源时(如动态链接库、执行文件、配置文件等)没有明确的指定资源的路径,而是依赖操作系统去搜索资源,这种行为可能被攻击者利用,通过在搜索优先级较高的目录放置不良资源,…...
Unity 2D实战小游戏开发跳跳鸟 - 记录显示最高分
上一篇文章中我们实现了游戏的开始界面,在开始界面中有一个最高分数的UI,本文将接着实现记录最高分数以及在开始界面中显示最高分数的功能。 添加跳跳鸟死亡事件 要记录最高分,则需要在跳跳鸟死亡时去进行判断当前的分数是否是最高分,如果是最高分则进行记录,如果低于之前…...
openeuler 22.03 lts sp4 使用 cri-o 和 静态 pod 的方式部署 k8s-v1.32.0 高可用集群
前情提要 整篇文章会非常的长…可以选择性阅读,另外,这篇文章是自己学习使用的,用于生产,还请三思和斟酌 静态 pod 的部署方式和二进制部署的方式是差不多的,区别在于 master 组件的管理方式是 kubectl 还是 systemctl有 kubeadm 工具,为什么还要用静态 pod 的方式部署?…...
穷举vs暴搜vs深搜vs回溯vs剪枝系列一>黄金矿工
目录 决策树:代码设计代码: 决策树: 代码设计 代码: class Solution {boolean[][] vis;int ret,m,n;public int getMaximumGold(int[][] grid) {m grid.length;n grid[0].length;vis new boolean[m][n]; for(int i 0; i <…...
SQL Server配置管理器无法连接到 WMI 提供程序
目录 第一步第二部 第一步 发现没有资源管理器 在文件夹找到管理器 打开发现报这个错误 配置管理器无法连接到 WMI 提供程序第二部 https://blog.csdn.net/thb369208315/article/details/126954074...
微信小程序获取openid和其他接口同时并发请求如何保证先获取到openid
在微信小程序中,如果你需要并发请求获取 openid 和其他接口的数据,并且希望确保先获取到 openid 之后再进行后续操作,可以考虑以下几种方法: 方法一:使用 Promise 链 1, 先请求 openid:使用 Promise 来请求 openid。 2, 在获取到 openid 后再请求其他接口。 function g…...
为AI聊天工具添加一个知识系统 之87 详细设计之28 Derivation 统一建模元模型 之1
文本要点 要点 Derivation 统一建模元模型 Derivation 统一建模元模型:意识原型的祖传代码,即支撑 程序框架的 符号学中的 自然和逻辑树。 这棵树的雏形中描述了三种建模工件:语用钩子,语法糖和语义胶水。 三种工件对应的三“…...