【练习】【回溯:组合:一个集合 元素可重复】力扣 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
输出: []
来源:力扣 39. 组合总和
思路(注意事项)
const vector<int>& candidates
& 是引用符号。当一个函数参数被声明为引用类型时,函数内部使用的实际上是传入实参的别名,而不是实参的副本。这意味着对引用参数的修改会直接影响到原始的实参。引用传递避免了对象的复制,在处理大型对象时可以显著提高性能,减少内存开销。
- 在同一个集合中求组合,一定要有
start(目的是为了避免重复组合)
纯代码
class Solution {
private:vector<int> path;vector<vector<int>> ans;void backtracking (const vector<int>& candidates, int target, int sum, int start){if (sum > target) return;if (sum == target){ans.push_back(path);return;}for (int i = start; i < candidates.size() && target >= sum + candidates[i]; i ++){sum += candidates[i];path.push_back(candidates[i]);backtracking (candidates, target, sum, i);sum -= candidates[i];path.pop_back();}}
public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {sort (candidates.begin(), candidates.end());backtracking (candidates, target, 0, 0);return ans;}
};
题解(加注释)
class Solution {
private:vector<int> path; // 存储当前组合路径vector<vector<int>> ans; // 存储所有符合条件的组合// 回溯函数// candidates: 候选数字集合(已排序)// target: 目标总和// sum: 当前路径元素和// start: 当前遍历起始索引(避免重复组合)void backtracking(vector<int> candidates, int target, int sum, int start) { // 注意这里 candidates 是值传递,会产生拷贝// 剪枝:当前和超过目标值,直接返回if (sum > target) return;// 终止条件:当前和等于目标值,记录结果if (sum == target) {ans.push_back(path);return;}// 遍历候选数字(从start开始,避免重复组合)for (int i = start; i < candidates.size() && target >= sum + candidates[i]; // 关键剪枝:提前终止无效分支i++) {sum += candidates[i]; // 选择当前数字path.push_back(candidates[i]);backtracking(candidates, target, sum, i); // 递归处理(注意传i而不是i+1,允许重复选择)sum -= candidates[i]; // 撤销选择path.pop_back();}}public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {// 关键优化:排序候选数组,方便后续剪枝sort(candidates.begin(), candidates.end());backtracking(candidates, target, 0, 0);return ans;}
};
相关文章:
【练习】【回溯:组合:一个集合 元素可重复】力扣 39. 组合总和
题目 组合总和 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。 candidates 中的 同一个 数字可以 无限制重…...
Mac 清理缓存,提高内存空间
步骤 1.打开【访达】 2.菜单栏第五个功能【前往】,点击【个人】 3.【command shift J】显示所有文件,打开【资源库】 4.删除【Containers】和【Caches】文件 Containers 文件夹:用于存储每个应用程序的沙盒数据,确保应用程序…...
数据结构——二叉树经典习题讲解
各位看官早安午安晚安呀 如果您觉得这篇文章对您有帮助的话 欢迎您一键三连,小编尽全力做到更好 欢迎您分享给更多人哦 大家好,我们今天来学习java数据结构的二叉树 递归很重要的一些注意事项: 1:递归你能不能掌握在于࿱…...
神经网络八股(三)
1.什么是梯度消失和梯度爆炸 梯度消失是指梯度在反向传播的过程中逐渐变小,最终趋近于零,这会导致靠前层的神经网络层权重参数更新缓慢,甚至不更新,学习不到有用的特征。 梯度爆炸是指梯度在方向传播过程中逐渐变大,…...
堆、优先队列、堆排序
堆: 定义: 必须是一个完全二叉树(完全二叉树:完全二叉树只允许最后一行不为满,且最后一行必须从左往右排序,最后一行元素之间不可以有间隔) 堆序性: 大根堆:每个父节点…...
vue 学习-vite api.js
/** 整机管理 * */ // 整机分类 列表 export const wholeMachineServersType params > ajaxGet({url: wholeMachine/serverstype/,params}) // 整机分类 新增 export const wholeMachineServersTypeAdd params > ajaxPost({url: wholeMachine/serverstype/,params}) /…...
java练习(35)
ps:题目来自力扣 整数反转 给你一个 32 位的有符号整数 x ,返回将 x 中的数字部分反转后的结果。 如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ,就返回 0。 假设环境不允许存储 64 位整数(有符号或无符号)…...
PW_Balance
目录 1、 PW_Balance 1.1、 getDocumentsTypeID 1.2、 getShouldAmount 1.3、 setOptimalAmount 1.4、 setRemark PW_Balance package com.gx.pojo; public class PW_Balance { private Integer BalanceID; private Integer PaymentID; private Integer ReceptionID…...
【Linux-网络】HTTP的清风与HTTPS的密语
🎬 个人主页:谁在夜里看海. 📖 个人专栏:《C系列》《Linux系列》《算法系列》 ⛰️ 道阻且长,行则将至 目录 📚 引言 📚 一、HTTP 📖 1.概述 📖 2.URL ǵ…...
【前端框架】vue2和vue3的区别详细介绍
Vue 3 作为 Vue 2 的迭代版本,在性能、语法、架构设计等多个维度均有显著的变革与优化。以下详细剖析二者的区别: 响应式系统 Vue 2 实现原理:基于 Object.defineProperty() 方法实现响应式。当一个 Vue 实例创建时,Vue 会遍历…...
CMake管理依赖实战:多仓库的无缝集成
随着软件复杂度的增加,单个项目可能需要依赖多个外部库或模块。这些依赖项可能是来自不同的代码仓库,如ATest和BTest。为了实现高效的依赖管理,CMake提供了多种方式来处理这种多仓库的情况。下面我们将详细介绍几种常见的方法,并通…...
Touchgfx 编写下载算法文件(.stldr)
一)下载算法文件主要参考官方的STM32 ST-LINK Utility模板:(文件所在位置如下:) C:\Program Files (x86)\STMicroelectronics\STM32 ST-LINK Utility\ST-LINK Utility\ExternalLoader\M25P64_STM3210E-EVAL\Project\MD…...
回不去的乌托邦
回不去的乌托邦 坐在电脑面前愣神间已至深夜,依然睡意不起。 相比于带着疲惫入睡,伏案发呆更令人惬意。想起最近在自媒体上看到的一句话“最顶级的享受变成了回不去的乌托邦”。 “这是兄弟们最后一次逛校园了,我拍个照”。我的记忆力总是用在…...
如何在 SpringBoot 项目使用 Redis 的 Pipeline 功能
本文是博主在批量存储聊天中用户状态和登陆信息到 Redis 缓存中时,使用到了 Pipeline 功能,并对此做出了整理。 一、Redis Pipeline 是什么 Redis 的 Pipeline 功能可以显著提升 Redis 操作的性能,性能提升的原因在于可以批量执行命令。当我…...
Linux----线程
一、基础概念对比 特性进程 (Process)线程 (Thread)资源分配资源分配的基本单位(独立地址空间)共享进程资源调度单位操作系统调度单位CPU调度的最小单位创建开销高(需复制父进程资源)低(共享进程资源)通信…...
实现rolabelimg对于dota格式文件的直接加载和保存
在本篇博客中,我们将讲解如何修改roLabelImg.py文件,使其能够直接加载和保存Dota格式的标注文件(txt)以替换掉复杂的xml文件。通过对源代码的修改,我们将实现支持加载并保存Dota格式标注数据,以便与roLabel…...
bboss v7.3.5来袭!新增异地灾备机制和Kerberos认证机制,助力企业数据安全
ETL & 流批一体化框架 bboss v7.3.5 发布,多源输出插件增加为特定输出插件设置记录过滤功能;Elasticsearch 客户端新增异地双中心灾备机制,提升框架高可用性;Elasticsearch client 和 http 微服务框架增加对 Kerberos 认证支持…...
华为昇腾服务器固件Firmware、驱动Drive、CANN各自的作用与联系?
文章目录 **1. 固件(Firmware)****2. 驱动(Driver)****3. CANN(Compute Architecture for Neural Networks)****三者关系****典型问题定位** 华为昇腾服务器的固件、驱动和CANN是支撑其AI计算能力的核心组件…...
MySQL 视图入门
一、什么是 MySQL 视图 1.1 视图的基本概念 在 MySQL 中,视图是一种虚拟表,它本身并不存储实际的数据,而是基于一个或多个真实表(基表)的查询结果集。可以把视图想象成是一个预定义好的查询语句的快捷方式。当你查询…...
算法很美笔记(Java)——动态规划
解重叠子问题(当前解用到了以前求过的解) 形式:记忆型递归或递推(dp) 动态规划本质是递推,核心是找到状态转移的方式,也就是填excel表时的逻辑(填的方式),而…...
Python|GIF 解析与构建(5):手搓截屏和帧率控制
目录 Python|GIF 解析与构建(5):手搓截屏和帧率控制 一、引言 二、技术实现:手搓截屏模块 2.1 核心原理 2.2 代码解析:ScreenshotData类 2.2.1 截图函数:capture_screen 三、技术实现&…...
设计模式和设计原则回顾
设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...
《Playwright:微软的自动化测试工具详解》
Playwright 简介:声明内容来自网络,将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具,支持 Chrome、Firefox、Safari 等主流浏览器,提供多语言 API(Python、JavaScript、Java、.NET)。它的特点包括&a…...
LeetCode - 394. 字符串解码
题目 394. 字符串解码 - 力扣(LeetCode) 思路 使用两个栈:一个存储重复次数,一个存储字符串 遍历输入字符串: 数字处理:遇到数字时,累积计算重复次数左括号处理:保存当前状态&a…...
浅谈不同二分算法的查找情况
二分算法原理比较简单,但是实际的算法模板却有很多,这一切都源于二分查找问题中的复杂情况和二分算法的边界处理,以下是博主对一些二分算法查找的情况分析。 需要说明的是,以下二分算法都是基于有序序列为升序有序的情况…...
C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。
1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj,再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...
中医有效性探讨
文章目录 西医是如何发展到以生物化学为药理基础的现代医学?传统医学奠基期(远古 - 17 世纪)近代医学转型期(17 世纪 - 19 世纪末)现代医学成熟期(20世纪至今) 中医的源远流长和一脉相承远古至…...
嵌入式学习笔记DAY33(网络编程——TCP)
一、网络架构 C/S (client/server 客户端/服务器):由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序,负责提供用户界面和交互逻辑 ,接收用户输入,向服务器发送请求,并展示服务…...
【 java 虚拟机知识 第一篇 】
目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...
(一)单例模式
一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...
