您现在的位置是:首页 > 正文

Leetcode刷题详解——子集

2024-04-01 04:43:36阅读 2

1. 题目链接:78. 子集

2. 题目描述:

给你一个整数数组 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 中的所有元素 互不相同

3. 解法1:

3.1 算法思路:

为了获取nums数组的所有子集,我们需要对数组的每个元素进行选择或不选择的操作,即nums数组一定存在2^(数组长度)个子集。对于查找子集,具可以定义一个数组,来记录当时的状态,并对其进行递归。

3.2 递归流程:

  1. 递归结束条件:如果当前需要处理的元素下标越界,则记录当前状态并直接返回
  2. 在递归过程中,对于每个元素,我们有两种选择:
    1. 不选择当前元素,直接递归到下一个元素
    2. 选择当前元素,将其添加到数组末尾后递归到下一个元素,然后在递归结束时撤回添加操作
  3. 所有符合条件的状态都将被记录下来,返回即可

请添加图片描述

3.3 C++算法代码:

class Solution {
    vector<vector<int>> ret; // 存储所有子集的结果
    vector<int> path; // 当前路径(即当前子集)
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums,0); // 从第一个元素开始进行深度优先搜索
        return ret; // 返回所有子集的结果
    }
    void dfs(vector<int>&nums,int pos)
    {
        if(pos==nums.size()) // 如果已经遍历完所有元素
        {
            ret.push_back(path); // 将当前路径(即当前子集)添加到结果中
            return; // 结束当前递归
        }
        // 选
        path.push_back(nums[pos]); // 将当前元素添加到当前路径中
        dfs(nums,pos+1); // 继续向下一层递归,处理下一个元素
        path.pop_back(); // 恢复现场,即移除当前路径中的最后一个元素
        // 不选
        dfs(nums,pos+1); // 继续向下一层递归,处理下一个元素,但不将当前元素添加到当前路径中
    }
};

4. 解法2:

4.1 算法思路:

对于每个元素有两种选择:

  1. 不进行任何操作;

  2. 将其添加至当前状态的集合。

    在递归时我们需要保证递归结束时当前的状态与进行递归操作前的状态不变,而当我们在选择进行步骤2进行递归时,当前状态会发生变化,因此我们需要在递归结束时撤回添加操作,即进行回溯

请添加图片描述

4.2 C++算法代码:

class Solution {
    vector<vector<int>> ret; // 存储所有子集的结果
    vector<int> path; // 当前路径(即当前子集)
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums,0); // 从第一个元素开始进行深度优先搜索
        return ret; // 返回所有子集的结果
    }
    void dfs(vector<int>&nums,int pos)
    {
        ret.push_back(path); // 将当前路径添加到结果中
        for(int i=pos;i<nums.size();i++) // 遍历从pos开始的剩余元素
        {
            path.push_back(nums[i]); // 将当前元素添加到当前路径中
            dfs(nums,i+1); // 继续向下一层递归,处理下一个元素
            path.pop_back(); // 恢复现场,即移除当前路径中的最后一个元素
        }
    }
};

网站文章

  • 计算机毕业设计/课程设计系列基于SpringBoot的校园问答论坛管理系统

    计算机毕业设计/课程设计系列基于SpringBoot的校园问答论坛管理系统

    本课程演示的是一款基于SpringBoot的校园问答论坛管理系统,主要针对计算机相关专业的正在做毕设的学生与需要项目实战练习的 Java 学习者。1. 包含:项目源码、项目文档、数据库脚本、软件工具等...

    2024-04-01 04:43:28
  • DVWA渗透测试演示(中)

    DVWA渗透测试演示(中)

    续DVWA渗透测试演示(上):六、DVWA之FileInclusion:(1)实验原理:PHP文件包含漏洞的产生原因是在通过PHP函数引入文件时,由于传入的文件名没有经过合理的校验,从而操作了预料之外...

    2024-04-01 04:42:53
  • [计算机网络]应用层协议,HTTP,SMTP,DNS

    [计算机网络]应用层协议,HTTP,SMTP,DNS

    应用层应用层协议原理网络应用程序体系结构规定如何在各种端系统上组织应用程序,由研发者设计客户机/服务器服务器:对外提供服务的一系列硬件和软件客户机:使用服务器提供的服务服务器7*24小时提供服务永久性...

    2024-04-01 04:42:47
  • VS 2005中使用C#创建及调用WebService完整实例

    关于WebService的概念及相关说明,在这里就不多说了,直接说如何实现IIS配置安装IIS(Windows 默认安装即可),确认可以从其他IP访问本机的默认主页,安装ASP.NET 2.0到IIS...

    2024-04-01 04:42:40
  • win10如何调整计算机时间同步,Win10系统如何设置时间同步间隔?修改时间同步频率的方法...

    win10如何调整计算机时间同步,Win10系统如何设置时间同步间隔?修改时间同步频率的方法...

    Win10系统如何设置时间同步间隔?如果系统时间并没有那么精确,偏差很多,你一定会去勾选“自动同步时间”的功能吧?!可是左等右等也不见调整时间,是这项功能没用吗?其实系统时间同步的频率是有间隔的,且这...

    2024-04-01 04:41:58
  • ES集群中节点与分片的区别

    ES集群中节点与分片的区别

    ES集群中节点与分片的区别 一开始我也搞混了,以为分片就是节点 节点:节点就是我们一个个的主机,你也可以理解为一个个的ES 分片:分片就是将原来存放在一个节点上面的数据进行分片,然后存放到不同的节点。...

    2024-04-01 04:41:50
  • android 从视频中提取音频及录音后合并到视频

    1.前段时间想开发一个app,用来提取mp4中的音频然后进行裁剪MediaExtractor extractor = new MediaExtractor();//新建提取器extractor.setDataSource(…);int numTracks = extractor.getTrackCount();for (int i = 0; i < numTracks; ++i) ...

    2024-04-01 04:41:44
  • MySQL可重复读和读已提交实现原理,深入理解MVCC。

    MySQL可重复读和读已提交实现原理,深入理解MVCC。

    1.隔离级别 MySQL中隔离级别分为4种,提未交读、读已提交、可重复读、串行化。同时MySQL默认隔离级别为可重复读。 图片 查看MySQL隔离级别 SELECT @@tx_isolation 设置...

    2024-04-01 04:41:03
  • Hadoop实训任务3:HDFS和MapReduce综合操作

    Hadoop实训任务3:HDFS和MapReduce综合操作

    Hadoop实训任务3:HDFS和MapReduce综合操作

    2024-04-01 04:40:56
  • Mybatis快速入门(二)

    Mybatis快速入门(二)

    第四章 动态SQL什么是动态SQL:同一个dao的方法,根据不同的条件可以表示不同的sql与语句,主要是where部分有变化,使用mybatis提供的标签实现动态sql的能力,主要讲if,where,...

    2024-04-01 04:40:50