每日刷题(回溯法经典问题之子集)

                                        食用指南:本文为作者刷题中认为有必要记录的题目

                                        前置知识回溯法经典问题之组合

                                       ♈️今日夜电波:想着你—郭顶

                                                                1:09 ━━━━━━️💟──────── 4:15
                                                                    🔄   ◀️   ⏸   ▶️    ☰ 

                                      💗关注👍点赞🙌收藏您的每一次鼓励都是对我莫大的支持😍 


目录

回溯法的理解

💮 一、子集

🌺二、子集II


回溯法的理解

 本文参考了一位大佬的题解,详细的介绍了回溯法:链接

上一篇刷题文: 回溯法经典问题之组合

        记住一句话:for循环横向遍历,递归纵向遍历,回溯不断调整结果集。 这句话将从始至终贯穿我们对于以上问题的回溯解决办法。 


💮 一、子集

题目链接:78. 子集

题目描述:

        给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1:

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

示例 2:

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

提示:

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

本题思路:

        采用经典的“回溯三部曲”:

        1、定义两个全局变量,一个用来存放符合条件单一结果(path),一个用来存放符合条件结果的集合(result)。注意要记得用一个变量来记录遍历的位置。

        2、回溯的主体,回溯终止条件。path保存一组数据,每次遍历到叶子节点,再插入到result中,并且回溯到上一个节点。

        3、单层搜索的过程。for循环用来横向遍历,递归的过程是纵向遍历。

      特别注意: 本题虽然同之前的组合问题差不多,但是还是需要做一定的变化的,依据题意,我们都知道任何一个子集都是包涵空集的,并且子集中一个元素也算子集。

         于是根据题意写出以下题解:

class Solution {
private:
vector<int> path;
vector<vector<int>> result;void backtrack(vector<int>& nums,int index)
{result.push_back(path);   if(index==nums.size()){return;}for(int i=index;i<nums.size();i++){path.push_back(nums[i]);backtrack(nums,i+1);path.pop_back();}}
public:vector<vector<int>> subsets(vector<int>& nums) {path.clear();result.clear();sort(nums.begin(),nums.end());backtrack(nums,0);return result;}
};


🌺二、子集II

题目链接:90. 子集 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

  本题思路:

        同样采用经典的“回溯三部曲”,但是由于此题中的元素是可以重复的,那这样必然会出现重复的子集,因此我们需要进行剪枝操作。此时可以参考 回溯法经典问题之组合 中最后一题。我们也建立一个used,用于标记是否使用过使用过元素。

         特别注意: 本题虽然同之前的题差不多,但是还是需要做一定的变化的。比如插入的操作。

        一图了解题解 ~(以{1,2,2}为例)

class Solution {
private:
vector<int> path;
vector<vector<int>> result;
void backtrack(vector<int>& nums,int index,vector<bool>& used)
{result.push_back(path);if(index==nums.size()){return;}for(int i=index;i<nums.size();i++){if(i>0&&nums[i-1]==nums[i]&&used[i-1]==0)continue;path.push_back(nums[i]);used[i]=1;backtrack(nums,i+1,used);used[i]=0;path.pop_back();}
}
public:vector<vector<int>> subsetsWithDup(vector<int>& nums) {path.clear();result.clear();vector<bool> used;used.resize(nums.size());sort(nums.begin(),nums.end());backtrack(nums,0,used);return result;}
};


                感谢你耐心的看到这里ღ( ´・ᴗ・` )比心,如有哪里有错误请踢一脚作者o(╥﹏╥)o!  

                                 

                                                                 给个三连再走嘛~      

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

jmeter setUp Thread Group

SetUp Thread Group 是一种特殊类型的线程组&#xff0c;它用于在主测试计划执行之前执行一些初始化任务。 SetUp Thread Group 通常用于以下几种情况&#xff1a; 用户登录&#xff1a;在模拟用户执行实际测试之前&#xff0c;模拟用户登录到系统以获取访问权限。 创建会话&a…

freertos之资源管理

中断屏蔽 屏蔽中断函数 在任务中使用 taskENTER_CRITICA()/taskEXIT_CRITICAL() 在中断中使用 taskENTER_CRITICAL_FROM_ISR()/taskEXIT_CRITICAL_FROM_ISR() 功能介绍 使用上述函数&#xff0c;进入临界中断&#xff0c;任务不会切换&#xff0c;且中断优先级处于con…

Ubuntu入门04——目录与文件

目录 1.显示当前工作目录 2.更改目录 3.创建工作目录 4.删除工作目录 5.移动文件或者文件夹 6.文件夹and文件查看命令 7. 回到根目录&#xff0c;回到上一级 8.删除工作目录 9.查看目录和文件 10.以树状图列出目录内容 11.文件查找 12.在数据库中查找文件或目录 1…

【大数据】Apache Iceberg 概述和源代码的构建

Apache Iceberg 概述和源代码的构建 1.数据湖的解决方案 - Iceberg1.1 Iceberg 是什么1.2 Iceberg 的 Table Format 介绍1.3 Iceberg 的核心思想1.4 Iceberg 的元数据管理1.5 Iceberg 的重要特性1.5.1 丰富的计算引擎1.5.2 灵活的文件组织形式1.5.3 优化数据入湖流程1.5.4 增量…

[移动通讯]【Carrier Aggregation-3】【5G】

前言&#xff1a; 参考&#xff1a; 5G Mobile Communications&#xff1a;《Carrier Aggregation in 5G》 目录&#xff1a; 1&#xff1a; carrier Allocation Schemes 2&#xff1a; 网络结构 3&#xff1a; LTE CA 4: 5G CA 一 Carrier Allocation Schemes CA 主要作用…

数学建模--非整数规划求解的Python实现

目录 1.算法流程简介 2.算法核心代码 3.算法效果展示 1.算法流程简介 #非线性规划模型求解: #我们采用通用的minimize函数来求解 #minimize(f,x,method,bounds,contrains) #f是待求函数 #x是代求的自变量 #method是求解方法 #bounds是取值范围边界 #contrains是约束条件 &q…

Java HashMap

简介 HashMap 是一个散列表&#xff0c;它存储的内容是键值对(key-value)映射。 HashMap 实现了 Map 接口&#xff0c;根据键的 HashCode 值存储数据&#xff0c;具有很快的访问速度&#xff0c;最多允许一条记录的键为 null&#xff0c;不支持线程同步。 HashMap 是无序的&…

新材料行业CRM客户管理系统的选择

新材料行业虽属小众细分市场&#xff0c;但其应用极广。更广阔的市场也意味着更激烈的竞争。新材料行业巨头林立&#xff0c;企业如何能脱颖而出&#xff1f;这里有一个适合新材料行业CRM系统推荐—Zoho CRM&#xff0c;帮助新材料企业推动业务高效运转的新模式。 数字化是企业…

Python爬虫乱码问题之encoding和apparent_encoding的区别

encoding是从http中的header中的charset字段中提取的编码方式&#xff0c;若header中没有charset字段则默认为ISO-8859-1编码模式&#xff0c;则无法解析中文&#xff0c;这是乱码的原因 apparent_encoding会从网页的内容中分析网页编码的方式&#xff0c;所以apparent_encodi…

Ubuntu之apt-get系列--apt-get安装软件的方法/教程

原文网址&#xff1a;Ubuntu之apt-get系列--apt-get安装软件的方法/教程_IT利刃出鞘的博客-CSDN博客 简介 本文介绍Ubuntu使用apt-get安装软件的方法。 安装软件 先更新列表 sudo apt-get update 安装软件 sudo apt-get install <package name>[<version>]…

windows查看端口占用,通过端口找进程号(查找进程号),通过进程号定位应用名(查找应用)(netstat、tasklist)

文章目录 通过端口号查看进程号netstat通过进程号定位应用程序tasklist 通过端口号查看进程号netstat 在Windows系统中&#xff0c;可以使用 netstat 命令来查看端口的占用情况。以下是具体的步骤&#xff1a; 打开命令提示符&#xff08;CMD&#xff09;&#xff1a;按WinR组…

绘制钻头芯厚变化图

import numpy as np import matplotlib.pyplot as plt posnp.array([0.05,0.5,0.97,3]) data_m1np.array([0.088,0.093,0.098,0.116]) data_m2data_m1-0.01 data_m3data_m1-0.02 fig plt.figure(figsize(5, 4)) plt.rcParams[xtick.direction] in # 将x周的刻度线方向设置向…

向量数据库Annoy和Milvus

Annoy 和 Milvus 都是用于向量索引和相似度搜索的开源库&#xff0c;它们可以高效地处理大规模的向量数据。 Annoy&#xff08;Approximate Nearest Neighbors Oh Yeah&#xff09;&#xff1a; Annoy 是一种近似最近邻搜索算法&#xff0c;它通过构建一个树状结构来加速最近…

并行和并发的区别

从操作系统的角度来看&#xff0c;线程是CPU分配的最小单位。 并行就是同一时刻&#xff0c;两个线程都在执行。这就要求有两个CPU去分别执行两个线程。并发就是同一时刻&#xff0c;只有一个执行&#xff0c;但是一个时间段内&#xff0c;两个线程都执行了。并发的实现依赖于…

旅游APP外包开发注意事项

旅游类APP通常具有多种功能&#xff0c;以提供给用户更好的旅行体验。以下分享常见的旅游类APP功能以及在开发和使用这些APP时需要注意的问题&#xff0c;希望对大家有所帮助。北京木奇移动技术有限公司&#xff0c;专业的软件外包开发公司&#xff0c;欢迎交流合作。 常见功能…

【HCIE】01.IGP高级特性

高级特性&#xff1a;一条命令解决一个问题 OSPF快速收敛机制 发生故障重新计算拓扑的过程叫做收敛&#xff0c;设备现在本身就是PRC算法和I-SPF算法 PRC&#xff08;针对叶子节点&#xff0c;叶子代表路由&#xff09; 不需要命令配置&#xff0c;就是ospf的特性&#xff…

LeetCode —— 复写零(双指针)

题目链接 力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 题目解析 将数组中出现的每个零复写一遍&#xff0c;然后将其他元素向右平移&#xff0c;数组长度不能改变。 法一&#xff1a;使用额外空间的做法 class Solution { public:void duplica…

Redis7入门概述

✅作者简介&#xff1a;大家好&#xff0c;我是Leo&#xff0c;热爱Java后端开发者&#xff0c;一个想要与大家共同进步的男人&#x1f609;&#x1f609; &#x1f34e;个人主页&#xff1a;Leo的博客 &#x1f49e;当前专栏&#xff1a; Java从入门到精通 ✨特色专栏&#xf…

DiffBIR: Towards Blind Image Restoration with Generative Diffusion Prior

DiffBIR: 基于生成扩散先验的盲图像恢复 论文链接&#xff1a;https://arxiv.org/abs/2308.15070 项目链接&#xff1a;https://github.com/XPixelGroup/DiffBIR Abstract 我们提出了DiffBIR&#xff0c;它利用预训练的文本到图像扩散模型来解决盲图像恢复问题。我们的框架采…

Golang单元测试举例

1.第一个例子 cal.go package mainfunc addUpper(n int) int {res : 0for i : 1; i < n; i {res i}return res }func getSub(n1 int, n2 int) int {return n1 - n2 }cal_test.go package main//测试文件名必须是_test.go结尾 //测试函数必须Test开头 import ("fmt…