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

回溯法---组合总和

题目:

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

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

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

思路:

全局变量result存储结果集,path存储某一组合

第一步:确定参数与返回值。参数为candidates数组,target,sum(path数组中现有值之和),startIndex(遍历的candidates数组下标起始),无返回值

第二步:确定终止条件。当target=sum时,获取到一个组合,将组合加入到结果集中

第三步:确定单层递归逻辑。for循环遍历candidates数组,从startIndex到candidates数组的最后一个元素。进行剪枝优化操作,当sum+candidates[i]>target时,就不必进行下去了。for循环里的步骤就是:更新sum,更新path,递归调用,回溯。

代码:

    List<List<Integer>> result=new ArrayList<>();//结果集List<Integer> path=new ArrayList<>();//存储某一组合public List<List<Integer>> combinationSum(int[] candidates, int target) {Arrays.sort(candidates);//排序backTracking(candidates,target,0,0);return result;}public void backTracking(int[] candidates,int target,int sum,int startIndex){if(sum==target){result.add(new ArrayList<>(path));return;}for(int i=startIndex;i<candidates.length&&sum+candidates[i]<=target;i++){sum+=candidates[i];path.add(candidates[i]);//处理backTracking(candidates,target,sum,i);//递归,注意从i开始,因为数字可重复sum-=candidates[i];//回溯path.remove(path.size()-1);}}

相关文章:

回溯法---组合总和

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

将Android Library项目发布到JitPack仓库

将项目代码导入Github 1.将本地项目目录初始化为 Git 仓库。 默认情况下&#xff0c;初始分支称为 main; 如果使用 Git 2.28.0 或更高版本&#xff0c;则可以使用 -b 设置默认分支的名称。 git init -b main 如果使用 Git 2.27.1 或更低版本&#xff0c;则可以使用 git symbo…...

JAVAWeb实战(后端篇)

因为前后端代码内容过多&#xff0c;这篇只写后端的代码&#xff0c;前端的在另一篇写 项目实战一&#xff1a; 1.创建数据库,表等数据 创建数据库 create database schedule_system 创建表&#xff0c;并添加内容 SET NAMES utf8mb4; SET FOREIGN_KEY_CHECKS 0;-- ---------…...

【vs】实用调试技巧——学会写优秀的代码!

&#x1f984;个人主页:小米里的大麦-CSDN博客 &#x1f38f;所属专栏:https://blog.csdn.net/huangcancan666/category_12718530.html ⚙️操作环境:Visual Studio 2022 目录 一、前言 二、什么是BUG&#xff1f; 三、调试是什么&#xff1f;有多重要&#xff1f; 一名优秀…...

数组声明方式

数组声明方式 一、 一维数组 元素数据类型[] 数组名; // 推荐元素数据类型 数组名[]; 二、 二维数组 元素数据类型[][] 数组名称; // 推荐元素数据类型 数组名称[][];元素数据类型[] 数组名称[]; 注&#xff1a; 对于第三种方式元素数据类型[] 数组名称[];&#xff0c;可…...

Docker中Docker网络-理解Docker0与自定义网络的使用示例

场景 CentOS7中Docker的安装与配置&#xff1a; CentOS7中Docker的安装与配置_centos docker sock-CSDN博客 在上面安装好Docker之后。 关于对Docker中默认docker0以及自定义网络的使用进行学习。 注&#xff1a; 博客&#xff1a;霸道流氓气质-CSDN博客 实现 理解dock…...

领域驱动大型结构之SYSTEM METAPHOR(系统隐喻)

在领域驱动设计&#xff08;Domain-Driven Design, DDD&#xff09;中&#xff0c;"System Metaphor" 是一种用于帮助开发团队和业务人员在理解和沟通系统时使用的概念模型。虽然 "System Metaphor" 并不是 DDD 的核心概念&#xff0c;但它在敏捷开发方法&…...

web前端开发一、VScode环境搭建

1、VScode安装live server插件&#xff0c;写完代码后&#xff0c;保存就会在浏览器自动更新&#xff0c;不需要再去浏览器点击刷新了 2、创建html文件 3、在文件中输入感叹号 &#xff01; 4、选择第一个&#xff0c;然后回车&#xff0c;就会自动输入html的标准程序 5、…...

DiAD代码use_checkpoint

目录 1、梯度检查点理解2、 torch.utils.checkpoint.checkpoint函数 1、梯度检查点理解 梯度检查点&#xff08;Gradient Checkpointing&#xff09;是一种深度学习优化技术&#xff0c;它的目的是减少在神经网络训练过程中的内存占用。在训练深度学习模型时&#xff0c;我们需…...

nginx出现Refused to apply inline style because it violates

Content Security Policy的错误。根据错误提示&#xff0c;nginx拒绝应用内联样式&#xff0c;因为它违反了内容安全策略&#xff08;Content Security Policy&#xff09;。内容安全策略是一种浏览器机制&#xff0c;用于防止潜在的安全漏洞&#xff0c;通过限制从外部来源加载…...

【中项第三版】系统集成项目管理工程师 | 第 11 章 规划过程组⑥ | 11.15 - 11.17

前言 第11章对应的内容选择题和案例分析都会进行考查&#xff0c;这一章节属于10大管理的内容&#xff0c;学习要以教材为准。本章上午题分值预计在15分。 目录 11.15 规划资源管理 11.15.1 主要输入 11.15.2 主要工具与技术 11.15.3 主要输出 11.16 估算活动资源 11.1…...

基础警务互联网app

智慧公安以大数据、云计算、人工智能、物联网和移动互联网技术为支撑&#xff0c;以“打、防、管、控”为目的&#xff0c;综合研判为核心&#xff0c;共享信息数据资源&#xff0c;融合业务功能&#xff0c;构建公安智慧大数据平台&#xff0c;实现公安信息数字化、网络化和智…...

为了方便写CURD代码,我在UTools写了个插件SqlConvert来生成代码!

-1. 前言 为了方便摸鱼&#xff0c;我之前写过一个通过sql生成代码的工具&#xff0c;但是服务器到期了&#xff0c;也就懒得重新部署了。 技术框架是 SpringBoot MybatisPlus Velocity Vue ElementUI Sql-ParseeSql-Parser-ui 0. Utools应用安装 官网地址: https://u.too…...

在国产芯片上实现YOLOv5/v8图像AI识别-【2.2】RK3588上C++开发环境准备及测试更多内容见视频

本专栏主要是提供一种国产化图像识别的解决方案&#xff0c;专栏中实现了YOLOv5/v8在国产化芯片上的使用部署&#xff0c;并可以实现网页端实时查看。根据自己的具体需求可以直接产品化部署使用。 B站配套视频&#xff1a;https://www.bilibili.com/video/BV1or421T74f 板子…...

2024数据资产入表财务实操手册

关注公众号《方案驿站》&#xff0c;并私信&#xff1a;2024数据资产入表财务实操手册&#xff0c;可获取本文pdf文件。...

react.16+

1、函数式组件 在vite脚手架中执行&#xff1a; app.jsx: import { useState } from react import reactLogo from ./assets/react.svg import viteLogo from /vite.svg import ./App.cssfunction App() {console.log(this)return <h2>我是函数式组件</h2> }exp…...

如何实现MySQL对某一张表的binlog日志进行记录

在 MySQL 中&#xff0c;使用触发器&#xff08;Triggers&#xff09;来记录表的变更是一种常见的方法。下面是具体的配置和步骤&#xff1a; 1. 创建日志表 首先&#xff0c;需要创建一个日志表&#xff0c;用于存储变更记录。 CREATE TABLE my_table_log (id INT AUTO_INC…...

使用requests库进行网络爬虫:入门指南

在数据收集与分析的广阔领域中&#xff0c;网络爬虫是一项基础而强大的技能。requests库是Python中用于发送HTTP请求的第三方库&#xff0c;它简洁易用&#xff0c;非常适合初学者学习网络爬虫。本文将带你一步步了解如何使用requests库进行基本的网络爬虫操作。 一、安装requ…...

实验5-1 使用函数计算两点间的距离

本题要求实现一个函数&#xff0c;对给定平面任意两点坐标(x1,y1)和(x2,y2)&#xff0c;求这两点之间的距离。 函数接口定义&#xff1a; double dist( double x1, double y1, double x2, double y2 );其中用户传入的参数为平面上两个点的坐标(x1, y1)和(x2, y2)&#xff0c;函…...

免费!OpenAI发布最新模型GPT-4o mini,取代GPT-3.5,GPT-3.5退出历史舞台?

有个小伙伴问我&#xff0c;GPT-4O mini是什么&#xff0c;当时我还一脸懵逼&#xff0c;便做了一波猜测&#xff1a; 我猜测哈&#xff0c;这个可能是ChatGPT4o的前提下&#xff0c;只支持文本功能的版本&#xff0c;速度更快 结果&#xff0c;大错特错。 让我们一起看看Open…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别

一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

C/C++ 中附加包含目录、附加库目录与附加依赖项详解

在 C/C 编程的编译和链接过程中&#xff0c;附加包含目录、附加库目录和附加依赖项是三个至关重要的设置&#xff0c;它们相互配合&#xff0c;确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中&#xff0c;这些概念容易让人混淆&#xff0c;但深入理解它们的作用和联…...

MFE(微前端) Module Federation:Webpack.config.js文件中每个属性的含义解释

以Module Federation 插件详为例&#xff0c;Webpack.config.js它可能的配置和含义如下&#xff1a; 前言 Module Federation 的Webpack.config.js核心配置包括&#xff1a; name filename&#xff08;定义应用标识&#xff09; remotes&#xff08;引用远程模块&#xff0…...

JUC并发编程(二)Monitor/自旋/轻量级/锁膨胀/wait/notify/锁消除

目录 一 基础 1 概念 2 卖票问题 3 转账问题 二 锁机制与优化策略 0 Monitor 1 轻量级锁 2 锁膨胀 3 自旋 4 偏向锁 5 锁消除 6 wait /notify 7 sleep与wait的对比 8 join原理 一 基础 1 概念 临界区 一段代码块内如果存在对共享资源的多线程读写操作&#xf…...