《程序员面试金典(第6版)》面试题 08.04. 幂集(回溯算法,位运算,C++)不断更新

题目描述

  • 幂集。编写一种方法,返回某集合的所有子集。集合中不包含重复的元素。

  • 说明:解集不能包含重复的子集。

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

解题思路与代码

  • 其实这道题,一看就是属于子集问题,让你在一个N个数的集合里有多少符合条件的子集。
  • 回溯算法是一种试探性的搜索算法,它在解决某些组合问题,字节问题,排列问题等时非常有效,所以呢,这道题,我们就可以去用回溯法去解决。

方法一 : 回溯法

这里就用我最崇拜的carl哥的回溯三部曲模版,来带大家解这道题。

第一步,找出回溯函数模板返回值
第二步,确定回溯函数终止条件
第三步,回溯搜索的遍历过程

关于回溯算法的参数,一般是在写回溯逻辑的时候,发现缺哪个参数就加哪个参数的。不存在与在哪一个步骤就一定要确定好参数是啥。

这个是回溯法的大致模版

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
        处理节点;
        backtracking(路径,选择列表); // 递归
        回溯,撤销处理结果
    }
}

这道题具体的代码如下:

class Solution {
public:
    vector<vector<int>> result;
    vector<vector<int>> subsets(vector<int>& nums) {
        if(nums.empty()) return {};
        int begin = 0;
        int end = nums.size();
        vector<int> vec;
        result.push_back({});
        backtracking(nums,vec,begin,end);
        return result;
    }
    void backtracking(vector<int>& nums,vector<int>& vec,int begin,int end){
        if(begin >= end) 
            return;
        for(int i = begin; i < end; ++i){
            vec.push_back(nums[i]);
            result.push_back(vec);
            backtracking(nums,vec,++begin,end);
            vec.pop_back();
        }
    }
};
  • 需要特别注意的是,在backtracking(nums,vec,++begin,end);这一行代码中,需要特别注意第二个传入参数

  • 这里可以写 ++ begini + 1 但是不能去写 begin + 1,这是因为,当我们使用++begin作为递归调用的参数时,begin的值在循环迭代中会被改变,而使用begin + 1作为参数时,begin的值在循环迭代中保持不变。这是它们之间的关键区别。

  • 使用++begin能够得到正确的结果,因为它确保了begin在每次递归调用之后递增。这样,当递归返回到当前层次时,begin的值已经递增了,从而避免了重复子集的产生。

  • 而使用begin + 1作为参数,在递归调用时虽然传递了正确的下一个值,但在循环迭代中,begin的值保持不变。这导致递归返回到当前层次时,重复使用了相同的begin值,从而产生了重复的子集。

  • i + 1 也能达到与++begin同样的效果,这是因为,它们之间都可以保证每次递归调用都是从当前元素的下一个元素开始,所以是对的。而不是从下一个元素开始,这将导致生成重复的子集。

在这里插入图片描述

复杂度分析

  • 时间复杂度:
    对于给定长度为n的nums数组,这段代码会生成所有可能的子集。子集的个数是2n,因为每个元素都有两种选择:包含在子集中或不包含。在这个实现中,我们使用回溯法遍历所有可能的子集。在最坏的情况下,我们需要遍历所有子集并将它们添加到结果集合中。因此,时间复杂度为O(2n * n),其中O(2^n)是遍历所有子集的时间,O(n)是在每次递归调用中复制子集到结果集合的时间。

  • 空间复杂度:
    递归栈空间:在最坏的情况下,递归栈的深度等于数组的长度n,因此递归栈空间复杂度为O(n)。
    结果集合空间:有2^n 个子集。由于子集中的元素总数是固定的,即n个元素,所以实际上我们不需要将每个子集的大小计入空间复杂度。因此,结果集合的空间复杂度应为O(2^n)。

综上所述,这段代码的空间复杂度应为O(n + 2^n)。递归栈空间为O(n),结果集合空间为O( 2^ n) 。

总结

这道题是一道很好的拿回溯模版练手的好题。可以更好的去理解回溯算法。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

博客让谷歌或是百度收录

参考以下大佬的博客教程 Hexo框架(六)&#xff1a;SEO优化及站点被搜索引擎收录设置 | 你真是一个美好的人类 第一步 安装百度和 Google 的站点地图生成插件&#xff1a; npm install hexo-generator-baidu-sitemap --save npm install hexo-generator-sitemap --save 然后来…

文件或目录损坏且无法读取错误的恢复方法

我们在日常的生活当中经常都会遇到各种各样的问题。比如有些时候将磁盘插入电脑之后突然跳出来一个“磁盘结构损坏且无法读取”的提示框&#xff0c;那么像这个情况该怎么解决呢?别着急&#xff0c;小编现在就将磁盘结构损坏且无法读取这个问题的解决方法来分享给你们 文件或目…

数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列(核心思路、解题过程、完整题解)

目录 用队列实现栈 题目描述 题目示例 核心思路 解题过程 定义结构体 创建栈结构体函数 入栈函数 出栈函数 取栈顶数据函数 判断栈是否为空函数 销毁栈函数 完整题解&#xff08;C语言&#xff09; 用栈实现队列 题目描述 题目示例 核心思路 完整题解…

计算机网络管理 ARP 地址解析协议 ARP的基础原理 Wireshark ARP 报文分析 ARP的通信过程

⬜⬜⬜ ---&#x1f7e7;&#x1f7e8;&#x1f7e9;&#x1f7e6;&#x1f7ea; (*^▽^*)欢迎光临 &#x1f7e7;&#x1f7e8;&#x1f7e9;&#x1f7e6;&#x1f7ea;---⬜⬜⬜ ✏️write in front✏️ &#x1f4dd;个人主页&#xff1a;陈丹宇jmu &#x1f381;欢迎各位→…

GPT4和ChatGPT的区别,太让人震撼

文 | Serendipity知乎 前言 GPT4上午朋友圈已经刷屏啦&#xff0c;不过我还在忙&#xff0c;刚刚才登上 GPT-4 &#xff0c;现在来体验一下~ 附 GPT-4 能力测试站&#xff08;无需魔法&#xff0c;仅供国内研究测试&#xff09;&#xff1a; https://gpt4test.com 附 Cha…

解决代码重复的优化方案

上周公司组织培训Spring 基于注解的数据校验方案&#xff0c;可以节省很大工作量&#xff0c;其实&#xff0c;除了数据校验&#xff0c;还有很多其他方案&#xff0c;可以大幅提高代码的整洁性。如&#xff1a;设计模式、OOP 思想、反射、泛型等等&#xff0c;框架往往需要以同…

强化学习下的多教师知识蒸馏模型(学习笔记

对知识蒸馏的方法提出了一个新的方向 采用多个不同的教师模型同时训练一个学生模型 一个很明显的好处 就是 多个教师model可以减少单个教师模型它的bias 但是当我们有多个老师的时候&#xff0c; 学生模型是否能够根据自己的能力选择和结合教师模型的特点 来选择性的向老师…

Maven依赖管理

文章目录一、mvn依赖的特性1. 依赖的范围2. 依赖的传递3. 依赖的排除二、mvn中的继承和聚合1. 聚合2. 继承3. Demo1、首先创建一个父工程并且修改它的打包方式为 pom2、创建子模块工程3、依赖管理三、企业级知识扩展1. 属性2. 版本管理3. 资源配置4. 多环境开发配置Maven工程约…

SWAT模型(高阶)

SWAT模型高阶十七项案例分析实践应用 导师&#xff1a;刘老师【副教授】&#xff1a;来自国内双一流高校&#xff0c;长期从事数字流域建模、流域水土过程模拟、遥感及GIS技术应用等领域工作&#xff0c;发表多篇SCI论文暨完成多项科研项目&#xff0c;具有资深的技术底蕴和专…

Python 01 初识python

目录 一、编程是怎么来到我们这个世界的&#xff1f; 二、Python的由来&#xff1f; 三、什么是python&#xff1f; 3.1面向对象和面向过程 3.1.1面向对象 3.1.2 面向过程 3.2解释性 3.2.1 编译性 3.2.2 解释性 3.3交互式 四、Python3和Python2 五、python和其他…

基于LiFePO4和硅/还原氧化石墨烯纳米复合材料的锂离子电池

A lithium-ion battery based on LiFePO4 and silicon/reduced graphene oxide nanocomposite highlights&#xff1a; 硅纳米颗粒(nSi)和还原氧化石墨烯(RGO)作为阳极&#xff1b;微波辐射&#xff0c;对混合物进行热处理&#xff0c;合成nSi/RGO复合物&#xff1b;通过不同充…

Jsoup使用教程以及使用案例

文章目录1&#xff1a;什么是Jsoup1&#xff1a;Jsoup概述2&#xff1a;Jsoup能做什么2&#xff1a;Jsoup相关概念3&#xff1a;获取文档1&#xff1a;导入jsoup的jar包2&#xff1a;从URL中加载文档对象&#xff08;常用&#xff09;3&#xff1a;从本地文件中加载文档对象4&a…

2023 海外工具站 3 月复盘

3 月的碎碎念&#xff0c;大致总结了商业人生、付费软件、创业方向选择、创业感性还是理性、如何解决复杂问题及如何成长这几个方面的内容。 商业人生 商业人生需要试错能力和快速信息收集与验证校准&#xff1b; 商业逻辑需要试错能力&#xff0c;收集各种渠道信息后整理决…

手把手教你一步一步暴力破解密码,学不会来找我

目录 一、什么是暴力破解&#xff1f; 二、暴力破解弱口令实验 三、如何防御暴力破解攻击&#xff1f; 一、什么是暴力破解&#xff1f; 暴力破解也可称为穷举法、枚举法&#xff0c;是一种针对于密码的破译方法&#xff0c;将密码进行逐个推算直到找出真正的密码为止。设置长而…

[学习笔记] 3. C++ / CPP提高

本阶段主要针对C泛型编程和STL技术做详细讲解&#xff0c;探讨C更深层的使用。 [学习笔记] 3. C / CPP提高1. 模板1.1 模板的概念1.2 函数模板1.2.1 函数模板语法1.2.2 函数模板注意事项1.2. 3函数模板案例1.2.4 普通函数与函数模板的区别1.2.5 普通函数与函数模板的调用规则1.…

HTML标签

目录 1.注释标签 2.标题标签:h1-h6 3.段落标签 4.换行标签 5.转义字符 6.格式化标签 7.图片标签:img 8.超链接便签:a 9.表格标签 10.列表标签 11.表单标签 12.无语义标签:div&span 1.注释标签 <!-- 我是注释 --> ctrl/快捷键可以快速进行注释/取消注释 …

PVE虚拟机安装爱快/iKuai软路由(爱快软路由虚拟机系统安装教程)

上篇提到PVE后&#xff0c;装LINUX CENTOS8&#xff0c;现在装个爱快软路由. 一、软硬件要求 1、安装好PVE虚拟环境的X86系统&#xff0c;32位爱快系统需要512MB以上内存&#xff0c;64位爱快系统需要4GB以上。 2、双网口主板&#xff0c;如果是单网口要配置openwrt/LEDE为单…

【C语言编程练习】手撕扫雷

【C语言编程练习】手撕扫雷一、目标二、具体实现步骤1、棋盘的设计思路2、选定模式3、创建及初始化棋盘4、布置雷到棋盘5、打印棋盘6、排查雷7、递归版统计雷数8、判断是否胜出的函数三、完整代码逻辑展示1、Minesweeping.h2、Minesweeping.c3、test.c一、目标 之所以打算将扫…

板内盘中孔设计狂飙,细密间距线路中招

一博高速先生成员&#xff1a;王辉东大风起兮云飞扬&#xff0c;投板兮人心舒畅。赵理工打了哈欠&#xff0c;伸了个懒腰&#xff0c;看了看窗外&#xff0c;对林如烟说道&#xff1a;“春天虽美&#xff0c;但是容易让人沉醉。如烟&#xff0c;快女神节了&#xff0c;要不今晚…

AHP层次分析法分析流程

AHP层次分析法分析流程&#xff1a; 一、案例背景 当前有一项研究&#xff0c;想要构建公司绩效评价指标体系&#xff0c;将一级指标分为4个&#xff0c;分别是&#xff1a;服务质量、管理水平、运行成本、安全生产&#xff0c;现在想要确定4个指标的权重。 AHP层次分析法是一…
最新文章