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

Leetcode JAVA刷刷站(39)组合总和

一、题目概述

二、思路方向

       为了解决这个问题,我们可以使用回溯算法来找到所有可能的组合,使得组合中的数字之和等于目标数 target。因为数组中的元素可以无限制地重复选择,所以在回溯过程中,我们不需要跳过已经选择的元素,而是可以从当前位置开始继续选择。

三、代码实现  

import java.util.ArrayList;  
import java.util.Arrays;  
import java.util.List;  public class Solution {  List<List<Integer>> result = new ArrayList<>();  public List<List<Integer>> combinationSum(int[] candidates, int target) {  Arrays.sort(candidates); // 对数组进行排序,有助于提前结束回溯  List<Integer> tempList = new ArrayList<>();  backtrack(candidates, target, 0, tempList);  return result;  }  private void backtrack(int[] candidates, int remain, int start, List<Integer> tempList) {  if (remain < 0) {  return; // 如果剩余需要达到的和已经是负数,则剪枝  }  if (remain == 0) {  result.add(new ArrayList<>(tempList)); // 如果剩余需要达到的和为0,则找到了一种符合条件的组合  return;  }  for (int i = start; i < candidates.length; i++) {  // 因为元素可以重复选择,所以我们不需要跳过已经选择过的元素  // 但可以通过排序和剪枝来避免不必要的搜索  if (i > start && candidates[i] == candidates[i - 1]) {  continue; // 跳过重复的元素,避免产生重复的组合  }  tempList.add(candidates[i]);  backtrack(candidates, remain - candidates[i], i, tempList); // 注意这里是从i开始,允许选择相同的数字  tempList.remove(tempList.size() - 1); // 回溯,撤销选择  }  }  public static void main(String[] args) {  Solution solution = new Solution();  int[] candidates = {2, 3, 6, 7};  int target = 7;  List<List<Integer>> combinations = solution.combinationSum(candidates, target);  for (List<Integer> combination : combinations) {  System.out.println(combination);  }  }  
}

执行结果: 

四、小结

       在这个解决方案中,我们首先对数组进行排序,这是为了在处理过程中能够更方便地进行剪枝和跳过重复元素。然后,我们使用一个递归函数 backtrack 来遍历所有可能的组合。在递归函数中,我们检查当前的和是否等于目标值,或者是否已经是负数(如果是负数则剪枝)。然后,我们遍历数组,从当前位置开始选择元素,并递归地调用 backtrack 函数,传入剩余需要达到的和、下一个开始的位置(允许选择相同的数字)、以及当前的组合列表。最后,在回溯过程中,我们需要撤销选择,以便尝试其他可能的组合。

       注意,在这个解决方案中,我们使用了 List<List<Integer>> 来存储所有可能的组合,并且使用 ArrayList 作为内部的临时列表来构建每个组合。在找到一种符合条件的组合时,我们通过创建一个新的 ArrayList 实例来将其添加到结果列表中,以避免在后续的回溯过程中修改已经添加到结果列表中的组合。

 结语 

只有流过血的手指

才能弹出世间的绝唱

!!!

相关文章:

Leetcode JAVA刷刷站(39)组合总和

一、题目概述 二、思路方向 为了解决这个问题&#xff0c;我们可以使用回溯算法来找到所有可能的组合&#xff0c;使得组合中的数字之和等于目标数 target。因为数组中的元素可以无限制地重复选择&#xff0c;所以在回溯过程中&#xff0c;我们不需要跳过已经选择的元素&#x…...

Spring中AbstractAutowireCapableBeanFactory

AbstractAutowireCapableBeanFactory 是 Spring 框架中的一个抽象类&#xff0c;位于 org.springframework.beans.factory.support 包中。它实现了 AutowireCapableBeanFactory 接口&#xff0c;提供了一些通用的方法和逻辑&#xff0c;以支持 Spring 中的自动装配功能。 主要…...

PostgreSQL的walwriter和archiver进程区别

PostgreSQL的walwriter和archiver进程区别 在PostgreSQL中&#xff0c;walwriter和archiver进程是两个重要的后台进程&#xff0c;它们负责管理WAL&#xff08;Write-Ahead Logging&#xff0c;预写日志&#xff09;文件&#xff0c;但它们的职责和功能有所区别。理解这两个进…...

前端字体没有授权,字体版权检测(是否为方正字体)

1.截图系统中的首页和登录页面&#xff0c;主要是有字体的地方 2.在线字体版权检测地址&#xff1a;字体版权自动检测-求字体网 3.上传照片&#xff0c;开始对图片进行检测&#xff0c;每个账号有三次免费次数 4.检测完&#xff0c;直接查看检测报告即可&#xff0c; 报告中…...

在 SOCKS 和 HTTP 代理之间如何选择?

在 SOCKS 和 HTTP 代理之间进行选择需要彻底了解每种代理的工作原理以及它们传达的配置。只有这样&#xff0c;您才能轻松地在不同类型的代理之间进行选择。 本文概述了 HTTP 和 SOCKS 代理是什么、它们如何运作以及它们各自带来的好处。此外&#xff0c;我们将比较这两种代理类…...

C++适配windows和linux下网络编程TCP简单案例

C网络编程 网络协议是计算机网络中通信双方必须遵循的一套规则和约定&#xff0c;用于实现数据的传输、处理和控制。这些规则包括了数据格式、数据交换顺序、数据处理方式、错误检测和纠正等。网络协议是使不同类型的计算机和网络设备能够相互通信的基础&#xff0c;是网络通信…...

OpenDDS的GUID是如何构造的?

1、GUID、RepoID、GUID_t概念和关系 GUID(Global Unique IDentifiers)是RTPS规范约定的DDS对象的唯一性ID;RepoId(Repository IDentifiers)是Repo服务约定的DDS对象的唯一性ID;GUID和RepoId,都是基于GUID_t结构体定义,名称不同,但实质上是一样的。题外话: 无论是GUID还…...

初识MySQL(安装与配置环境)

嗨&#xff01;今天我们进入一个新的领域---数据库。 首先来个小小铺垫。 我们平时存储东西的时候&#xff0c;一般用到文件。为什么有文件了&#xff0c;还继续要这个数据库呢&#xff1f; 很明显&#xff0c;文件有一些不好的地方&#xff0c;需要数据库来进行补充。 文件…...

druid+logback打印sql执行日志

druid 的LogFilter 为我们准备了四种logger类型&#xff0c;对应打印 datasource相关、connection相关、statement相关、resultset相关的日志。 druid.sql.Datasource&#xff1a;打印数据源相关的字段。 druid.sql.Connection&#xff1a;打印应用程序获得数据库连接的过程。…...

C++编程:无锁环形队列 (LockFreeRingQueue)的简单实现、测试和分析

文章目录 0. 概述1. 无锁环形队列概述1.1 无锁环形队列的特点1.2 无锁环形队列的优势与局限 2. LockFreeRingQueue 实现2.1 Enqueue 操作流程图2.2 Dequeue 操作流程图 3. 核心实现细节3.1 环形队列的大小调整3.2 索引计算3.3 原子操作与CAS3.4 线程让步 4. 测试示例程序4.1 实…...

植物生长时为什么会扭动?科学家解开令查尔斯·达尔文困惑的千古之谜

在一项新的研究中&#xff0c;来自美国和以色列的物理学家可能已经弄清了植物生长过程中的一种古怪行为–也是查尔斯-达尔文本人在其生命的最后几十年里所好奇的一个谜&#xff1a;对于许多人类来说&#xff0c;植物可能看起来静止不动&#xff0c;甚至有点无趣。但实际上&…...

SAP LE学习笔记02 - WM和库存管理(IM)之间的关系,保管Lot(Quant)

上一章学习了LE的基础知识。 1&#xff0c;LE的概述&#xff0c;LE里面包含下面3个大的模块 - LE-WM 仓库管理 / - LE-SHP 发货/ - LE-TRA 运输 2&#xff0c;仓库的结构 - 仓库番号 / -保管域Type(存储区域)/ - 保管区画(存储区)/ - 棚番&#xff08;Storage Bin 仓位&…...

Span<T> 是 C# 7.2 引入的重要类型

Span<T> 是 C# 7.2 引入的一个非常重要的类型&#xff0c;它提供了一种低开销、类型安全的方式来操作连续的内存区域。Span<T> 本质上是一个结构体&#xff0c;它封装了一个内存段的引用&#xff08;通过指针&#xff09;以及该内存段的长度。由于它直接操作内存&a…...

Python办公自动化:初识 `openpyxl`

1.1 什么是 openpyxl&#xff1f; openpyxl 是一个用于读写 Excel 2010 xlsx/xlsm/xltx/xltm 文件的 Python 库。它允许我们通过 Python 脚本自动化处理 Excel 文件&#xff0c;包括创建新的工作簿、修改现有的工作簿、格式化单元格、处理公式和图表等功能。这对于办公自动化、…...

Pocketbase实战体验:内置数据库与实时功能如何超越传统MySQL

Pocketbase 是一个开源的实时后端服务器&#xff0c;内置了数据库、实时订阅、用户认证、RESTful API 等功能&#xff0c;而 MySQL 是一个广泛使用的关系数据库管理系统。以下是 Pocketbase 相对于 MySQL 的一些潜在优点&#xff1a; 完整的后端解决方案 一体化&#xff1a;P…...

ChatGPT 3.5/4.0 新手使用手册(详细版)

1. 什么是 ChatGPT&#xff1f; ChatGPT是由 OpenAI 开发的先进人工智能语言模型&#xff0c;能够理解并生成自然语言文本。它可以帮助你进行写作、回答问题、提供建议&#xff0c;甚至参与对话。ChatGPT 3.5 和 4.0 是两个不同版本&#xff0c;它们都拥有强大的语言处理能力&…...

【Java学习】Stream流详解

所属专栏&#xff1a;Java学习 Stream流是JDK 8引入的一个概念&#xff0c;它提供了一种高效且表达力强的方式来处理数据集合&#xff08;如List、Set等&#xff09;或数组。Stream API可以以声明性方式&#xff08;指定做什么&#xff09;来处理数据序列。流操作可以被分为两大…...

Oracle(69)什么是表压缩(Table Compression)?

表压缩&#xff08;Table Compression&#xff09;是一种数据库优化技术&#xff0c;用于减少表数据的存储空间和提高I/O性能。通过压缩表数据&#xff0c;可以显著减少存储需求&#xff0c;并在某些情况下提高查询性能&#xff0c;特别是对于只读或主要是读取操作的表。表压缩…...

java JUC编程

Java并发工具包&#xff08;JUC&#xff09;&#xff0c;全称Java Util Concurrent&#xff0c;是Java提供的一个用于构建多线程应用程序的工具包&#xff0c;位于java.util.concurrent包及其子包中。 并发编程主要解决以下三个经典问题&#xff1a; 1. **原子性问题&#xf…...

vue3+element-plus表格分页选中加默认回显选中

1.需求 某个表单需要选择多条数据&#xff0c;点击选择按钮&#xff0c;弹框出来一个分页列表&#xff0c;选择多条数据&#xff0c;外面表单中显示选中的数据&#xff0c;可以删除数据&#xff0c;再次点击按钮&#xff0c;回显当前选中的数据。 2.解决办法 1.el-table加ro…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

前端倒计时误差!

提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

GitHub 趋势日报 (2025年06月08日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

BLEU评分:机器翻译质量评估的黄金标准

BLEU评分&#xff1a;机器翻译质量评估的黄金标准 1. 引言 在自然语言处理(NLP)领域&#xff0c;衡量一个机器翻译模型的性能至关重要。BLEU (Bilingual Evaluation Understudy) 作为一种自动化评估指标&#xff0c;自2002年由IBM的Kishore Papineni等人提出以来&#xff0c;…...

Leetcode33( 搜索旋转排序数组)

题目表述 整数数组 nums 按升序排列&#xff0c;数组中的值 互不相同 。 在传递给函数之前&#xff0c;nums 在预先未知的某个下标 k&#xff08;0 < k < nums.length&#xff09;上进行了 旋转&#xff0c;使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...

基于鸿蒙(HarmonyOS5)的打车小程序

1. 开发环境准备 安装DevEco Studio (鸿蒙官方IDE)配置HarmonyOS SDK申请开发者账号和必要的API密钥 2. 项目结构设计 ├── entry │ ├── src │ │ ├── main │ │ │ ├── ets │ │ │ │ ├── pages │ │ │ │ │ ├── H…...

文件上传漏洞防御全攻略

要全面防范文件上传漏洞&#xff0c;需构建多层防御体系&#xff0c;结合技术验证、存储隔离与权限控制&#xff1a; &#x1f512; 一、基础防护层 前端校验&#xff08;仅辅助&#xff09; 通过JavaScript限制文件后缀名&#xff08;白名单&#xff09;和大小&#xff0c;提…...