力扣--深度优先算法/回溯算法78.子集

news/2024/7/20 20:17:26 标签: 算法, leetcode, 深度优先, c语言, 数据结构, c++

思路分析:

  1. 首先,定义了一个类 Solution,其中包含一个成员变量 result 用于存储最终的所有子集。
  2. 在类中定义了一个私有成员函数 dfs,用于执行深度优先搜索,生成所有可能的子集。
  3. 主函数 subsets 初始化结果,将空集加入 result,然后调用 dfs 从数组的起始位置开始生成子集。
  4. 深度优先搜索函数中,从当前位置开始遍历数组,将当前元素加入当前子集,将当前子集加入结果,然后递归调用,从下一个位置开始生成子集。
  5. 在递归过程中,使用回溯来处理当前元素加入子集后的情况,确保每一步都能够尝试所有可能的元素。
  6. 最终,返回存储所有子集的结果。

class Solution {
    // 用于存储最终结果的二维数组
    vector<vector<int>> result;
    
    // 用于暂存当前子集的一维数组
    vector<int> path;
    
    // 深度优先搜索函数,用于生成所有子集
    void dfs(vector<int>& nums, int start) {
        // 从给定的起始位置开始遍历数组
        for (int i = start; i < nums.size(); i++) {
            // 将当前元素加入当前子集
            path.push_back(nums[i]);
            
            // 将当前子集加入最终结果
            result.push_back(path);
            
            // 递归调用,从下一个位置开始生成子集
            dfs(nums, i + 1);
            
            // 回溯,将当前元素从子集中移除,继续尝试其他可能的元素
            path.pop_back();
        }
        return;
    }

public:
    // 主函数,生成给定数组的所有子集
    vector<vector<int>> subsets(vector<int>& nums) {
        // 首先将空集加入结果
        result.push_back({});
        
        // 调用深度优先搜索函数,从数组的起始位置开始生成子集
        dfs(nums, 0);
        
        // 返回最终的结果
        return result;
    }
};


http://www.niftyadmin.cn/n/5423253.html

相关文章

C++_包装器

目录 1、包装器的用法 2、包装器的类型 3、包装器的作用 4、包装成员函数 5、bind&#xff08;绑定&#xff09; 5.1 bind的用法 5.2 bind减少参数个数 结语 前言&#xff1a; C11的包装器&#xff0c;总称为function包装器&#xff0c;而包装器又称适配器…

Spring Data的Repositories----自定义存储库实现

【Spring连载】使用Spring Data的Repositories----自定义存储库实现 一、定制单个存储库1.1 配置1.2 歧义的解决1.3 手动装配 二、自定义基础存储库 Spring Data提供了各种选项&#xff0c;可以用很少的编码来创建查询方法。但是&#xff0c;当这些选项不能满足你的需求时&…

Python 学习——Python BeautifulSoup 库文档

目录 一、 Beautiful Soup 4.4.0 文档1.1 寻求帮助 二、 快速开始三、 安装 Beautiful Soup3.1 安装完成后的问题3.2 安装解析器 四、 如何使用五、 对象的种类5.1 Tag5.1.1 Name5.1.2 Attributes5.1.3 多值属性 5.2 可以遍历的字符串5.3 BeautifulSoup5.4 注释及特殊字符串 六…

unity显示当前时间

1建立文本组件和一个空对象 2创建一个脚本并复制下面代码 using System.Collections; using System.Collections.Generic; using TMPro; using UnityEngine;public class showtime: MonoBehaviour {public TextMeshProUGUI time;private void Update(){string currentTime Sy…

Kafka常见使用问题

消息丢失 生产者方&#xff1a;设置ack为1或-1/all可以防止生产的消息丢失&#xff0c;如果要做到生产消息成功率提高到最高&#xff0c;ack设置成all&#xff0c;把min.insync.replicas配置成分区备份数&#xff0c;把ack设置成1或者-1/all&#xff0c;这样生产者生产的消息发…

Linux软件高级编程-网络--TCP通信--day14

TCP包头: 1.序号:发送端发送数据包的编号 2.确认号:已经确认接收到的数据的编号(只有当ACK为1时,确认号才有用) TCP为什么安全可靠: 1.在通信前建立三次握手连接 SYN SYNACK ACK 2.在通信过程中通过序列号和确认号保障数据传输的完整性 本次发送序列号:上次收到的确…

五子棋小游戏(sut实验报告)

实验目的 实现人与人或人与电脑进行五子棋对弈 实验内容 启动游戏&#xff0c;显示游戏参数设置界面&#xff0c;用户输入参数后进入游戏界面&#xff0c;显示棋盘及双方博弈过程&#xff0c;游戏过程中可选择退出游戏。判定一方获胜后结束本局游戏&#xff0c;可选择继续下…

蓝桥杯Python题目类型

"蓝桥杯"是一项全国性的软件编程竞赛&#xff0c;旨在促进软件和信息技术领域专业人才培养。由于每年的题目都会有所变化&#xff0c;我无法提供具体的蓝桥杯Python题目。但是&#xff0c;我可以告诉你一些通常出现在编程竞赛中的Python题目类型&#xff0c;以及你可…