当前位置: 首页 > 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…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

HashMap中的put方法执行流程(流程图)

1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中&#xff0c;其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下&#xff1a; 初始判断与哈希计算&#xff1a; 首先&#xff0c;putVal 方法会检查当前的 table&#xff08;也就…...

莫兰迪高级灰总结计划简约商务通用PPT模版

莫兰迪高级灰总结计划简约商务通用PPT模版&#xff0c;莫兰迪调色板清新简约工作汇报PPT模版&#xff0c;莫兰迪时尚风极简设计PPT模版&#xff0c;大学生毕业论文答辩PPT模版&#xff0c;莫兰迪配色总结计划简约商务通用PPT模版&#xff0c;莫兰迪商务汇报PPT模版&#xff0c;…...

路由基础-路由表

本篇将会向读者介绍路由的基本概念。 前言 在一个典型的数据通信网络中&#xff0c;往往存在多个不同的IP网段&#xff0c;数据在不同的IP网段之间交互是需要借助三层设备的&#xff0c;这些设备具备路由能力&#xff0c;能够实现数据的跨网段转发。 路由是数据通信网络中最基…...

基于 HTTP 的单向流式通信协议SSE详解

SSE&#xff08;Server-Sent Events&#xff09;详解 &#x1f9e0; 什么是 SSE&#xff1f; SSE&#xff08;Server-Sent Events&#xff09; 是 HTML5 标准中定义的一种通信机制&#xff0c;它允许服务器主动将事件推送给客户端&#xff08;浏览器&#xff09;。与传统的 H…...