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

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

oracle与MySQL数据库之间数据同步的技术要点

Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异&#xff0c;它们的数据同步要求既要保持数据的准确性和一致性&#xff0c;又要处理好性能问题。以下是一些主要的技术要点&#xff1a; 数据结构差异 数据类型差异&#xff…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

浅谈不同二分算法的查找情况

二分算法原理比较简单&#xff0c;但是实际的算法模板却有很多&#xff0c;这一切都源于二分查找问题中的复杂情况和二分算法的边界处理&#xff0c;以下是博主对一些二分算法查找的情况分析。 需要说明的是&#xff0c;以下二分算法都是基于有序序列为升序有序的情况&#xf…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...

return this;返回的是谁

一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请&#xff0c;不同级别的经理有不同的审批权限&#xff1a; // 抽象处理者&#xff1a;审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...

MeshGPT 笔记

[2311.15475] MeshGPT: Generating Triangle Meshes with Decoder-Only Transformers https://library.scholarcy.com/try 真正意义上的AI生成三维模型MESHGPT来袭&#xff01;_哔哩哔哩_bilibili GitHub - lucidrains/meshgpt-pytorch: Implementation of MeshGPT, SOTA Me…...

MLP实战二:MLP 实现图像数字多分类

任务 实战&#xff08;二&#xff09;&#xff1a;MLP 实现图像多分类 基于 mnist 数据集&#xff0c;建立 mlp 模型&#xff0c;实现 0-9 数字的十分类 task: 1、实现 mnist 数据载入&#xff0c;可视化图形数字&#xff1b; 2、完成数据预处理&#xff1a;图像数据维度转换与…...

【动态规划】B4336 [中山市赛 2023] 永别|普及+

B4336 [中山市赛 2023] 永别 题目描述 你做了一个梦&#xff0c;梦里有一个字符串&#xff0c;这个字符串无论正着读还是倒着读都是一样的&#xff0c;例如&#xff1a; a b c b a \tt abcba abcba 就符合这个条件。 但是你醒来时不记得梦中的字符串是什么&#xff0c;只记得…...