leetCode 78.子集 + 回溯算法 + 图解 + 笔记

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

示例 1:

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

示例 2:

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

 子集问题组合问题分割问题都可以抽象成一棵树,不同的是:

  • 组合问题和分割问题都是收集树形结构中的叶子节点的结果
  • 子集问题收集树形结构中的所有节点的结果

C++代码: 

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums,int startIndex) {
        result.push_back(path);// 收集子集,要放在终止添加的上面,否则会漏掉自己
        // if(startIndex>=nums.size()) return; // 终止条件可以不加
        for(int i=startIndex;i<nums.size();i++) {
            path.push_back(nums[i]); // 子集收集元素
            backtracking(nums,i+1);  // 注意从i+1开始,元素不重复取
            path.pop_back();         // 回溯
        }
        return;
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        backtracking(nums,0);
        return result;
    }
};
  • 时间复杂度: O(n * 2^n)
  • 空间复杂度: O(n)

疑惑:不写终止条件会不会无限递归?(来自代码随想录Carl老师的提问和解答)

答疑:并不会,因为每次递归的下一层就是从i+1开始的

参考和推荐文章、视频:

代码随想录代码随想录PDF,代码随想录百度网盘,代码随想录知识星球,代码随想录八股文PDF,代码随想录刷题路线,代码随想录知识星球八股文icon-default.png?t=N7T8https://www.programmercarl.com/0078.%E5%AD%90%E9%9B%86.html#%E6%80%9D%E8%B7%AF回溯算法解决子集问题,树上节点都是目标集和! | LeetCode:78.子集_哔哩哔哩_bilibiliicon-default.png?t=N7T8https://www.bilibili.com/video/BV1U84y1q7Ci/?spm_id_from=pageDriver&vd_source=a934d7fc6f47698a29dac90a922ba5a3

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

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

相关文章

智慧机场视频监控系统方案:AI智能助力机场智慧运营

一、方案背景 随着人们生活物质水平的上升&#xff0c;人们对机场的需求也日益增多&#xff0c;在民航新建、迁建、扩建机场项目猛增的同时&#xff0c;也需同步配备相应的安防监控系统&#xff0c;以满足民航机场安全管理要求和机场运营业务的高速发展。 二、方案概述 智慧机…

【服务部署】常用内网穿透方案

一、前言 由于一些开发及使用需求&#xff0c;需要将内网机器端口映射到公网&#xff0c;达到公网访问内网环境的目的 本文主要介绍几种常用的内网穿透方案 ssh远程端口转发 部署简单&#xff0c;无需额外安装软件包 frp反向代理 功能配置丰富&#xff0c;部署相对复杂&#…

frp 配置内网访问

frp介绍 frp 是一个开源、简洁易用、高性能的内网穿透软件&#xff0c;支持 tcp, udp, http, https 等协议。frp 项目官网是 https://github.com/fatedier/frp 下载地址&#xff1a; https://github.com/fatedier/frp/releases frp工作原理 服务端运行&#xff0c;监听一个…

键盘敲入一个字母,操作系统发生了什么?

一、设备控制器 我们的电脑设备可以接非常多的输入输出设备&#xff0c;比如鼠标键盘网卡硬盘打印机等&#xff0c;每个设备的用法和功能都不相同&#xff0c;那操作系统是如何把这些输入输出设备统一管理的呢&#xff1f; 为了屏蔽设备之间的差异&#xff0c;每个设备都有一…

前端项目环境的搭建

一、下载并且安装Node&#xff08;不安装node&#xff0c;就安装nvm。nvm安装教程&#xff09;&#xff1a; 1.官网下载Node&#xff1a;https://nodejs.org/en/ 2.测试nodejs安装是否成功&#xff1a; 在windows powerShell中输入node -v 和 npm -v&#xff0c;看到版本号就…

【23-24 秋学期】NNDL 作业9 RNN - SRN

简单循环网络&#xff08;Simple Recurrent Network&#xff0c;SRN&#xff09;只有一个隐藏层的神经网络&#xff0e; 目录 1. 实现SRN &#xff08;1&#xff09;使用Numpy &#xff08;2&#xff09;在1的基础上&#xff0c;增加激活函数tanh &#xff08;3&#xff0…

rabbitMQ镜像队列的使用

在rabbitMQ集群中&#xff0c;默认发送消息时&#xff0c;队列默认时在一个节点上存在的。 我们以node01 node02 node03三节点集群为例&#xff0c;在node01声明队列发送消息后&#xff0c;发现&#xff1a; 测试队列只在节点node01上出现。 我们手动停止node01后&#xff0c…

#HarmonyOS:软件安装window和mac预览Hello World

Window软件地址 https://developer.harmonyos.com/cn/develop/deveco-studio#download 安装的建议 这个界面这样选&#xff0c;其他界面全部按照默认路径往下走&#xff01;&#xff01;&#xff01; 等待安装… 安装环境错误处理 一般就是本地node配置异常导致&#xff…

Nginx基线检查

扩展知识: Nginx主配置文件:/etc/nginx/nginx.conf 这是Nginx的主要配置文件,用于配置全局的设置、HTTP块、事件处理、邮件等内容。 打开并编辑配置文件 vim /etc/nginx/nginx.conf 一、关于禁止显示服务器版本号和操作系统版本信息: 简介: 在错误页面和响应头中显示…

SAP_ABAP_编程基础_逻辑流控制_比较运算符 / 比较字符串和数字串 / 比较二进制位结构 / 编程分支和循环

SAP ABAP 顾问&#xff08;开发工程师&#xff09;能力模型_Terry谈企业数字化的博客-CSDN博客文章浏览阅读470次。目标&#xff1a;基于对SAP abap 顾问能力模型的梳理&#xff0c;给一年左右经验的abaper 快速成长为三年经验提供超级燃料&#xff01;https://blog.csdn.net/j…

html/css中用float实现的盒子案例

运行效果&#xff1a; 代码部分&#xff1a; <!doctype html> <html> <head> <meta charset"utf-8"> <title>无标题文档</title> <style type"text/css">.father{width:300px; height:400px; background:gray;…

云轴科技ZStack助力龙芯打造IT产业新生态

11月28日&#xff0c;2023龙芯产品发布暨用户大会在国家会议中心启幕。大会以“到中流击水”为主题&#xff0c;现场发布新一代通用处理器龙芯3A6000、打印机主控芯片龙芯2P0500重磅成果&#xff0c;并对外公布龙芯处理器核IP及龙芯自主指令系统架构授权计划。作为龙芯的卓越行…

element-ui表格滚动效果,el-table滚动条样式重置

项目首页需要展示一个表格滚动区域&#xff0c;特此来记录一下 HTML <div class"table-box" mouseenter"mouseenter" mouseleave"mouseleave"><el-table :data"tableList" border height"400px" v-loading"…

spring日志输出到elasticsearch

1.maven <!--日志elasticsearch--><dependency><groupId>com.agido</groupId><artifactId>logback-elasticsearch-appender</artifactId><version>3.0.8</version></dependency><dependency><groupId>net.l…

单机zk安装与zk四字命令

一、下载 Apache ZooKeeper可以在 Linux 系统中使用 wget 命令直接下载&#xff0c;官网地址 Apache ZooKeeper 二、解压 tar -zxvf apache-zookeeper-3.8.3-bin.tar.gz 进去解压的目录中&#xff0c; 进入到 zk 解压目录的 conf 目录&#xff0c;复制 zoo_sample.cfg 文件&a…

leetCode 93.复原 IP 地址 + 回溯算法 + 图解 + 笔记

93. 复原 IP 地址 - 力扣&#xff08;LeetCode&#xff09; 有效 IP 地址 正好由四个整数&#xff08;每个整数位于 0 到 255 之间组成&#xff0c;且不能含有前导 0&#xff09;&#xff0c;整数之间用 . 分隔。 例如&#xff1a;"0.1.2.201" 和 "192.168.1.1…

基于AT89C51单片机的电子闹钟设计

1&#xff0e;设计任务 利用AT89C51单片机为核心控制元件,设计一个电子闹钟&#xff0c;设计的系统实用性强、操作简单&#xff0c;实现了智能化、数字化。 &#xff08;1&#xff09;按开始键自动进入时间显示&#xff0c;开始为0&#xff0c;按K1键进入更改时间&#xff0c…

代码随想录算法训练营 ---第五十一天

1.第一题&#xff1a; 简介&#xff1a; 本题相较于前几题状态复杂了起来&#xff0c;因为多了一个冷冻期。本题讲解可去代码随想录看&#xff0c;这里差不多只是加了些自己的理解。 动规五部曲&#xff0c;分析如下&#xff1a; 确定dp数组以及下标的含义 dp[i][j]&#x…

数据库应用:MongoDB 文档与索引管理

目录 一、理论 1.MongoDB文档管理 2.MongoDB索引管理 二、实验 1.MongoDB文档管理 2.MongoDB索引管理&#xff08;索引添加与删除&#xff09; 3.MongoDB索引管理&#xff08;全文索引&#xff09; 4.MongoDB索引管理&#xff08;多列索引&#xff09; 5.MongoDB索引管…

【办公软件】Outlook启动一直显示“正在启动”的解决方法

早上打开电脑Outlook2016以后&#xff0c;半个多小时了&#xff0c;一直显示这个界面&#xff1a; 解决办法 按WIN R键打开“运行”&#xff0c;输入如下命令&#xff1a; outlook.exe /safe 然后点击“确定” 这样就进入了Outlook的安全模式。 点击“文件”->“选项”-…
最新文章