当前位置: 首页 > news >正文

LeetCode 热题 100_组合总和(58_39_中等_C++)(递归(回溯))

LeetCode 热题 100_组合总和(58_39)

    • 题目描述:
    • 输入输出样例:
    • 题解:
      • 解题思路:
        • 思路一(递归(回溯)):
      • 代码实现
        • 代码实现(思路一(递归(回溯))):
        • 以思路一为例进行调试

题目描述:

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。

对于给定的输入,保证和为 target 的不同组合数少于 150 个。

输入输出样例:

示例 1:
输入:candidates = [2,3,6,7], target = 7
输出:[[2,2,3],[7]]
解释
2 和 3 可以形成一组候选,2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选, 7 = 7 。
仅有这两种组合。

示例 2:
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3:
输入: candidates = [2], target = 1
输出: []

提示:
1 <= candidates.length <= 30
2 <= candidates[i] <= 40
candidates 的所有元素 互不相同
1 <= target <= 40

题解:

解题思路:

思路一(递归(回溯)):

1、使用回溯的方法解组合问题时,最好的方法是画出递归树进行分析。
在这里插入图片描述
通过递归树不难分析出:
     ①、递归出口:sum==target(记录答案+回溯) 或者 sum>target(回溯)
我们可以记录path中的总和为sum,通过sum与target的比较来判断。也可以使用target-path数组中的元素与0进行比较来判断,其效果相同。
     ②、递归体:sum < target(查找可能的组合)

2、复杂度分析:
① 时间复杂度:O(S),其中 S 为所有可行解的长度之和(也就是递归树的节点数)。
② 空间复杂度:O(target)。除答案数组外,空间复杂度取决于递归的栈深度(也就是上图递归树的深度),在最差情况下需要递归 O(target) 层。

代码实现

代码实现(思路一(递归(回溯))):
class Solution {
private://记录其中一个组合vector<int> path;//记录所有满足组合总和的组合vector<vector<int>> ans;//递归(回溯)计算组合总和void backtracking(vector<int>& candidates, int target,int startIndex){//为目标数 “target” 的一个组合,存储到ans中if (target==0){     ans.emplace_back(path);return;}//当path中的数据大于“target”返回(path无需再添加元素,需减少元素)if (target<0) return;//注意这里i的开始位置,是为了避免出现“全排列”类型的重复for (int i = startIndex; i < candidates.size(); i++){path.emplace_back(candidates[i]);//继续添加其他元素,注意一个元素可以重复添加所以startIndex=ibacktracking(candidates,target - candidates[i],i);//回溯(和path.emplace_back(candidates[i])对应)path.pop_back();}}public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {//清空ans和path中的数据,防止上次调用存在数据残留ans.clear();path.clear();//递归(回溯)计算组合总和backtracking(candidates,target,0);return ans;}
};
以思路一为例进行调试
#include<iostream>
#include <vector>
using namespace std;class Solution {
private://记录其中一个组合vector<int> path;//记录所有满足组合总和的组合vector<vector<int>> ans;//递归(回溯)计算组合总和void backtracking(vector<int>& candidates, int target,int startIndex){//为目标数 “target” 的一个组合,存储到ans中if (target==0){     ans.emplace_back(path);return;}//当path中的数据大于“target”返回(path无需再添加元素,需减少元素)if (target<0) return;//注意这里i的开始位置,是为了避免出现“全排列”类型的重复for (int i = startIndex; i < candidates.size(); i++){path.emplace_back(candidates[i]);//继续添加其他元素,注意一个元素可以重复添加所以startIndex=ibacktracking(candidates,target - candidates[i],i);//回溯(和path.emplace_back(candidates[i])对应)path.pop_back();}}public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {//清空ans和path中的数据,防止上次调用存在数据残留ans.clear();path.clear();//递归(回溯)计算组合总和backtracking(candidates,target,0);return ans;}
};int main(int argc, char const *argv[])
{vector<int> candidates={2,3,5};int target=8;//计算组合总和Solution s;vector<vector<int>> ans=s.combinationSum(candidates,target);//输出计算的组合总和for (int i = 0; i < ans.size(); i++){cout<<"[";for (int j = 0; j < ans[i].size(); j++){cout<<ans[i][j];if (j!=ans[i].size()-1){cout<<" ";}}cout<<"]";}return 0;
}

LeetCode 热题 100_组合总和(58_39)原题链接
欢迎大家和我沟通交流(✿◠‿◠)

相关文章:

LeetCode 热题 100_组合总和(58_39_中等_C++)(递归(回溯))

LeetCode 热题 100_组合总和&#xff08;58_39&#xff09; 题目描述&#xff1a;输入输出样例&#xff1a;题解&#xff1a;解题思路&#xff1a;思路一&#xff08;递归&#xff08;回溯&#xff09;&#xff09;&#xff1a; 代码实现代码实现&#xff08;思路一&#xff08…...

使用PHP爬虫获取1688商品分类:实战案例指南

在电商领域&#xff0c;商品分类信息是商家进行市场调研、选品分析和竞争情报收集的重要基础。1688作为国内领先的B2B电商平台&#xff0c;提供了丰富且详细的商品分类数据。通过PHP爬虫技术&#xff0c;我们可以高效地获取这些分类信息&#xff0c;为商业决策提供有力支持。 …...

Nginx location 和 proxy_pass 配置详解

概述 Nginx 配置中 location 和 proxy_pass 指令的不同组合方式及其对请求转发路径的影响。 配置效果 1. location 和 proxy_pass 都带斜杠 / location /api/ {proxy_pass http://127.0.0.1:8080/; }访问地址&#xff1a;www.hw.com/api/upload转发地址&#xff1a;http://…...

云创智城充电系统:基于 SpringCloud 的高可用、可扩展架构详解-多租户、多协议兼容、分账与互联互通功能实现

在新能源汽车越来越普及的今天&#xff0c;充电基础设施的管理和运营变得越来越重要。云创智城充电系统&#xff0c;就像一个超级智能管家&#xff0c;为新能源充电带来了全新的解决方案&#xff0c;让充电这件事变得更方便、更高效、更安全。 一、厉害的技术架构&#xff0c;让…...

AIP-143 标准代号

编号143原文链接AIP-143: Standardized codes状态批准创建日期2019-07-24更新日期2019-07-24 许多常见的概念&#xff0c;如语言、国家、货币等&#xff0c;都有用于数据通信和处理的通用代号&#xff08;通常由国际标准化组织正式定义&#xff09;。这些代号解决了在书面语言…...

机器视觉--数字图像格式

图像格式 在数字图像的世界里&#xff0c;不同的图像格式有着各自的特点和适用场景。了解这些图像格式&#xff0c;对于我们在处理图像时选择合适的存储和传输方式至关重要。下面就让我们来详细探讨一下常见的几种数字图像格式。 一、BMP 文件&#xff08;Bitmap&#xff09;…...

Kotlin 2.1.0 入门教程(十七)接口

接口 接口可以包含抽象方法的声明&#xff0c;也可以包含方法的实现。 接口与抽象类的不同之处在于&#xff0c;接口无法存储状态。接口可以拥有属性&#xff0c;但这些属性要么必须是抽象的&#xff0c;要么就得提供访问器的实现。 接口使用 interface 关键字来定义&#x…...

渗透测试工具:SQLmap安装教程及使用

在渗透测试的世界里&#xff0c;SQL注入攻击无疑是最常见且最具威胁的安全漏洞之一。幸运的是&#xff0c;SQLmap 这个强大的自动化工具&#xff0c;能够帮助我们快速识别和利用这些漏洞。如果你也想了解如何用 SQLmap 进行渗透测试&#xff0c;那么这篇文章就是为你准备的&…...

4.SpringSecurity在分布式环境下的使用

参考 来源于黑马程序员&#xff1a; 手把手教你精通新版SpringSecurity 分布式认证概念说明 分布式认证&#xff0c;即我们常说的单点登录&#xff0c;简称SSO&#xff0c;指的是在多应用系统的项目中&#xff0c;用户只需要登录一次&#xff0c;就可以访 问所有互相信任的应…...

RocketMQ和Kafka如何实现顺序写入和顺序消费?

0 前言 先说明kafka&#xff0c;顺序写入和消费是Kafka的重要特性&#xff0c;但需要正确的配置和使用方式才能保证。本文需要解释清楚Kafka如何通过分区来实现顺序性&#xff0c;以及生产者和消费者应该如何配合。   首先&#xff0c;顺序写入。Kafka的消息是按分区追加写入…...

SQL联合查询

文章目录 MySQL系列&#xff1a;1.内连接2.外连接3.自连接4.子查询5.合并查询6.插入查询 MySQL系列&#xff1a; 初识MySQL&#xff0c;MySQL常用数据类型和表的操作&#xff0c;增删改查(CRUD)操作(总),数据库约束数据库设计 #班级表 drop table if exists class; create ta…...

deepseek:三个月备考高级系统架构师

一、备考总体规划&#xff08;2025年2月11日 - 2025年5月&#xff09; 1. 第一阶段&#xff1a;基础夯实&#xff08;2025年2月11日 - 2025年3月10日&#xff09; 目标&#xff1a;快速掌握系统架构师考试的核心知识点。 重点内容&#xff1a; 计算机组成原理、操作系统、数据…...

支持向量机原理

支持向量机&#xff08;简称SVM&#xff09;虽然诞生只有短短的二十多年&#xff0c;但是自一诞生便由于它良好的分类性能席卷了机器学习领域。如果不考虑集成学习的算法&#xff0c;不考虑特定的训练数据集&#xff0c;尤其在分类任务中表现突出。在分类算法中的表现SVM说是排…...

DeepSeek人工智能AI汽车营销销售培训讲师培训师唐兴通讲课汽车销售大数据存量客户数字化营销数字化销售大模型销售话术引流内容社群私域

唐兴通 数字商业创新实践专家、数字营销与销售顾问 沃顿商学院特邀演讲嘉宾&#xff5c;美国营销协会艾菲奖评委 核心专长&#xff1a; AI商业化应用、数字营销创新、数字新销售能力体系打造、数字化转型、 教学经历&#xff1a;从教20年&#xff0c;执教12所全球顶尖商学院…...

Molecular Communication(分子通信)与 Molecular Semantic Communication(分子语义通信)

1. 引言 随着传统无线通信在极端环境&#xff08;如微观生物体内、海洋深处&#xff09;中的局限性凸显&#xff0c;分子通信&#xff08;Molecular Communication, MC&#xff09;成为一种新型通信范式。分子通信通过分子作为信息载体&#xff0c;在纳米尺度上传输信息&#…...

Webpack代码分割、分割策略性能优化详解

在前端面试中,Webpack 是一个常见的考察点,特别是关于性能优化、构建配置以及代码分割等方面的问题。以下是 Webpack 常见问题详解,包括 代码分割 相关的内容。 1. Webpack 基础概念 1.1 Webpack 是什么? Webpack 是一个前端构建工具,主要用于将项目中的各种资源(JavaS…...

大脑网络与智力:基于图神经网络的静息态fMRI数据分析方法|文献速递-医学影像人工智能进展

Title 题目 Brain networks and intelligence: A graph neural network based approach toresting state fMRI data 大脑网络与智力&#xff1a;基于图神经网络的静息态fMRI数据分析方法 01 文献速递介绍 智力是一个复杂的构念&#xff0c;包含了多种认知过程。研究人员通…...

ArcGIS Pro显示缓存空间不足导致编辑或加载数据显示不完全

ArcGIS Pro对于显示缓存有32GB的限制&#xff0c;所以当缓存设置中&#xff0c;缓存将达到32GB时&#xff0c;会出现编辑、加载slpk显示不全的情况。 清除计算机上的显示缓存方法 1.启动 ArcGlS Pro。单击左下角的设置&#xff0c;然后单击选项&#xff1b; 2.在选项窗口中&…...

天童美语:观察你的生活

在孩子的认知里&#xff0c;世界宛如一片充满神秘色彩的未知之境&#xff0c;有着无尽的奥秘等待他们去探索。家长们&#xff0c;引导孩子用心观察世界&#xff0c;领略其中的美妙&#xff0c;这对孩子的成长进程有着极为关键的作用。贵阳天童教育相信&#xff1a;观察生活&…...

网络通信的基石:深入理解 TCP/IP 协议栈与 TCP/UDP 协议

博文题目:网络通信的基石:深入理解 TCP/IP 协议栈与 TCP/UDP 协议 引言 在当今数字化世界中,网络已经渗透到我们生活的方方面面。从浏览网页、收发邮件,到在线视频、远程会议,所有这些便捷的网络应用都离不开一个至关重要的基础设施——TCP/IP 协议栈。它就像是互联网的…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)

1.获取 authorizationCode&#xff1a; 2.利用 authorizationCode 获取 accessToken&#xff1a;文档中心 3.获取手机&#xff1a;文档中心 4.获取昵称头像&#xff1a;文档中心 首先创建 request 若要获取手机号&#xff0c;scope必填 phone&#xff0c;permissions 必填 …...

JS手写代码篇----使用Promise封装AJAX请求

15、使用Promise封装AJAX请求 promise就有reject和resolve了&#xff0c;就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...

腾讯云V3签名

想要接入腾讯云的Api&#xff0c;必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口&#xff0c;但总是卡在签名这一步&#xff0c;最后放弃选择SDK&#xff0c;这次终于自己代码实现。 可能腾讯云翻新了接口文档&#xff0c;现在阅读起来&#xff0c;清晰了很多&…...

解读《网络安全法》最新修订,把握网络安全新趋势

《网络安全法》自2017年施行以来&#xff0c;在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂&#xff0c;网络攻击、数据泄露等事件频发&#xff0c;现行法律已难以完全适应新的风险挑战。 2025年3月28日&#xff0c;国家网信办会同相关部门起草了《网络安全…...

论文阅读:LLM4Drive: A Survey of Large Language Models for Autonomous Driving

地址&#xff1a;LLM4Drive: A Survey of Large Language Models for Autonomous Driving 摘要翻译 自动驾驶技术作为推动交通和城市出行变革的催化剂&#xff0c;正从基于规则的系统向数据驱动策略转变。传统的模块化系统受限于级联模块间的累积误差和缺乏灵活性的预设规则。…...

学习一下用鸿蒙​​DevEco Studio HarmonyOS5实现百度地图

在鸿蒙&#xff08;HarmonyOS5&#xff09;中集成百度地图&#xff0c;可以通过以下步骤和技术方案实现。结合鸿蒙的分布式能力和百度地图的API&#xff0c;可以构建跨设备的定位、导航和地图展示功能。 ​​1. 鸿蒙环境准备​​ ​​开发工具​​&#xff1a;下载安装 ​​De…...

微服务通信安全:深入解析mTLS的原理与实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、引言&#xff1a;微服务时代的通信安全挑战 随着云原生和微服务架构的普及&#xff0c;服务间的通信安全成为系统设计的核心议题。传统的单体架构中&…...