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

代码随想录-Day27

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]]

方法:搜索回溯

class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> ans = new ArrayList<List<Integer>>();List<Integer> combine = new ArrayList<Integer>();dfs(candidates, target, ans, combine, 0);return ans;}public void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> combine, int idx) {if (idx == candidates.length) {return;}if (target == 0) {ans.add(new ArrayList<Integer>(combine));return;}// 直接跳过dfs(candidates, target, ans, combine, idx + 1);// 选择当前数if (target - candidates[idx] >= 0) {combine.add(candidates[idx]);dfs(candidates, target - candidates[idx], ans, combine, idx);combine.remove(combine.size() - 1);}}
}

这段代码是一个Java程序,实现了一个名为Solution的类,该类包含两个方法:combinationSumdfs。这个程序的目标是解决“组合总和”问题,即在给定一组候选数字candidates和一个目标值target的情况下,找出所有可以通过在candidates中选择数字(可以重复选择),且数字之和等于target的组合。返回的组合放在一个列表中,每个组合也是一个数字列表。

方法解析

  1. combinationSum方法

    • 输入int[] candidates(候选数字数组),int target(目标和)。
    • 输出List<List<Integer>>(所有和为目标值的组合列表)。
    • 逻辑:首先,初始化结果列表ans和一个临时组合列表combine。然后,调用深度优先搜索(DFS)方法dfs来递归寻找所有可能的组合。最后,返回结果列表ans
  2. dfs方法

    • 输入int[] candidatesint targetList<List<Integer>> ans(累计结果),List<Integer> combine(当前组合),int idx(当前搜索的起始下标)。
    • 逻辑
      • 基本情况:如果搜索到了数组末尾(idx == candidates.length),直接返回,表示这一分支搜索完毕。
      • 目标达成:如果当前目标和为0,说明找到了一个有效的组合,将当前组合添加到结果列表ans中,然后返回。
      • 递归搜索
        • 不选择当前数:直接跳过当前数,递归调用dfs方法进入下一个数字的搜索,即dfs(candidates, target, ans, combine, idx + 1)
        • 选择当前数:如果当前数可以用于减小目标和(即target - candidates[idx] >= 0),则将当前数添加到组合中,并递归调用dfs方法以减去当前数的值继续搜索。搜索完成后,通过combine.remove(combine.size() - 1)移除最后添加的数,进行回溯,以尝试其他组合。

通过这种方式,程序能够有效地遍历所有可能的组合,找出所有满足条件的解,并返回这些组合。

相关文章:

代码随想录-Day27

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

TalkingData数据统计:洞察数字世界的关键工具

TalkingData数据统计&#xff1a;洞察数字世界的关键工具 在数字化时代&#xff0c;数据已成为推动社会进步和商业决策的核心动力。TalkingData作为国内领先的移动数据服务平台&#xff0c;为众多企业提供了全面、精准的数据统计服务。本文将深入探讨TalkingData数据统计的应用…...

printf 一次性写

PWN里printf漏洞感觉很小&#xff0c;可发现居然理解的不全。 一般情况下&#xff0c;当buf不在栈内时&#xff0c;就不能直接写指针。这时候需要用到rbp链或者argv链。一般操作是第一次改指针&#xff0c;第二次改数值。 DAS昨天这里只给了一次机会然后就exit了。今天ckyen给…...

【Axure高保真原型】切换查看大图列表

今天和大家分享切换查看大图列表的原型模板&#xff0c;我们可以点击列表里的图片查看对应的大图&#xff0c;点击左右箭头可以切换切换上一页或下一页&#xff0c;如果是首页会自动禁用左箭头&#xff0c;末尾页会自动禁用右箭头。这个原型模板是用中继器制作的&#xff0c;所…...

Ant-Design-Vue动态表头并填充数据

Ant-Design-Vue动态表头并填充数据 Ant-Design-Vue 是一个基于 Vue.js 的前端UI框架&#xff0c;它继承了 Ant Design 的优秀设计理念&#xff0c;并针对 Vue.js 进行了深度优化。在实际开发过程中&#xff0c;我们经常需要处理各种复杂的表格数据&#xff0c;而 Ant-Design-V…...

Python-匿名函数

一、概念 匿名函数造出来的是一个内存地址&#xff0c;且内存地址没有绑定任何名字&#xff0c;很快被当做垃圾清理掉。所以匿名函数只需要临时调用一次&#xff0c;而有名函数永久使用&#xff1b; 匿名函数一般和其他函数配合使用&#xff1b; # 有名函数def func(x, y):…...

探索Web3工具:正确使用区块链平台工具的秘诀

在当今日新月异的数字时代&#xff0c;区块链技术正以惊人的速度改变着我们的生活和工作方式。尤其对于那些想要踏入区块链世界的人来说&#xff0c;正确使用区块链平台工具至关重要。本文将向您介绍一些关键的Web3工具&#xff0c;并以TestnetX.com为例&#xff0c;展示如何利…...

器利而事善——datagrip 的安装以及连接mysql

一&#xff0c;安装 下载&#xff1a;直接到官网下载即可&#xff0c; 破解&#xff1a;这是破解连接&#xff1a;https://pan.baidu.com/s/11BgOMp4Z9ddBrXwCVhwBng &#xff0c;提取码&#xff1a;abcd&#xff1b; 下载后&#xff0c;选择倒数第三个文件&#xff0c;打开da…...

C++标准模板(STL)- 迭代器库-迭代器原语-用于指示迭代器类别的空类类型

迭代器库-迭代器原语 迭代器库提供了五种迭代器的定义&#xff0c;同时还提供了迭代器特征、适配器及相关的工具函数。 迭代器分类 迭代器共有五 (C17 前)六 (C17 起)种&#xff1a;遗留输入迭代器 (LegacyInputIterator) 、遗留输出迭代器 (LegacyOutputIterator) 、遗留向前…...

ClickHouse 使用技巧总结

文章目录 数据导入、导出技巧外部文件导入导技巧使用集成表引擎导入、导出数据 建表技巧表引擎选择技巧分区键选择技巧数据结构选择技巧分区技巧 高级技巧物化视图投影位图变更数据捕获 常见报错及处理方法 数据导入、导出技巧 外部文件导入导技巧 ClickHouse作为OLAP即席分析…...

论文浅尝 | THINK-ON-GRAPH:基于知识图谱的深层次且可靠的大语言模型推理方法...

笔记整理&#xff1a;刘佳俊&#xff0c;东南大学硕士&#xff0c;研究方向为知识图谱 链接&#xff1a;https://arxiv.org/pdf/2307.07697.pdf 1. 动机 本文是IDEA研究院的工作&#xff0c;这篇工作将知识图谱的和大语言模型推理进行了结合&#xff0c;在每一步图推理中利用大…...

前端科举八股文-VUE篇

前端科举八股文-VUE篇 Vue响应式的基本原理?computed和watch的区别computed和methods的区别Slot是什么 ? 作用域插槽是什么?组件缓冲keep-alive是什么&#xff1f; 讲讲原理v-if&#xff0c;v-show的区别v-modal如何实现双向绑定组件中的data属性为什么是一个函数而不是对象…...

Websocket服务端结合内网穿透发布公网实现远程访问发送信息

文章目录 1. Java 服务端demo环境2. 在pom文件引入第三包封装的netty框架maven坐标3. 创建服务端,以接口模式调用,方便外部调用4. 启动服务,出现以下信息表示启动成功,暴露端口默认99995. 创建隧道映射内网端口6. 查看状态->在线隧道,复制所创建隧道的公网地址加端口号7. 以…...

GitHub 的底层数据库从 MySQL 5.7 无缝升级到 MySQL 8.0 的实践经验

提到 MySQL 这个数据库软件&#xff0c;相信大家再熟悉不过了&#xff0c;不论是市场流行度还是占有率一直一来都非常靠前。 那再提到 MySQL 5.7 这个具体的版本&#xff0c;大家是不是也同样感到非常熟悉&#xff1f; 相信不少个人或者团队的生产环境所用的 MySQL 数据库也曾…...

概率图模型在自然语言处理中的应用

概率图模型在自然语言处理(NLP)中的应用广泛且重要,它结合了概率论和图论,为处理复杂系统中变量之间的概率依赖关系提供了有效的建模方法。以下是概率图模型在NLP中的几个主要应用,结合参考文章中的相关信息进行详细说明: 核心概念与分类: 概率图模型的核心思想是利用图…...

AI网络爬虫:对网页指定区域批量截图

对网页指定区域批量截图&#xff0c;可以在deepseek的代码助手中输入提示词&#xff1a; 你是一个Python编程专家&#xff0c;一步一步的思考&#xff0c;完成一个对网页指定区域截图的python脚本的任务&#xff0c;具体步骤如下&#xff1a; 设置User-Agent: Mozilla/5.0 (…...

centos系统清理docker日志文件

centos系统清理docker日志文件 1.查看docker根目录位置2.清理日志 1.查看docker根目录位置 命令&#xff1a;docker info ,将Docker Root Dir 的值复制下来。如果目录中包含 等特殊符号的目录&#xff0c;需要转义 2.清理日志 创建文件&#xff1a;vim docker_logs_clean.…...

算法金 | Python 中有没有所谓的 main 函数?为什么?

​大侠幸会&#xff0c;在下全网同名[算法金] 0 基础转 AI 上岸&#xff0c;多个算法赛 Top [日更万日&#xff0c;让更多人享受智能乐趣] 定义和背景 在讨论Python为何没有像C或Java那样的明确的main函数之前&#xff0c;让我们先理解一下什么是main函数以及它在其他编程语言…...

RocketMQ相关知识知多少

一、RocketMQ的定义 官网网址&#xff1a;领域模型概述 | RocketMQ Apache RocketMQ 自诞生以来&#xff0c;因其架构简单、业务功能丰富、具备极强可扩展性等特点被众多企业开发者以及云厂商广泛采用。历经十余年的大规模场景打磨&#xff0c;RocketMQ 已经成为业内共识的金…...

C++vector部分实现及感悟

myvector.h #pragma once #include<assert.h> #include<iostream> #include<vector> using namespace std; namespace bit {template<class T>//必须使用typename场景\template<typename T>与template<class T>一般情况下这两个通用&#…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端

&#x1f31f; 什么是 MCP&#xff1f; 模型控制协议 (MCP) 是一种创新的协议&#xff0c;旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议&#xff0c;它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

云原生玩法三问:构建自定义开发环境

云原生玩法三问&#xff1a;构建自定义开发环境 引言 临时运维一个古董项目&#xff0c;无文档&#xff0c;无环境&#xff0c;无交接人&#xff0c;俗称三无。 运行设备的环境老&#xff0c;本地环境版本高&#xff0c;ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...

虚拟电厂发展三大趋势:市场化、技术主导、车网互联

市场化&#xff1a;从政策驱动到多元盈利 政策全面赋能 2025年4月&#xff0c;国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》&#xff0c;首次明确虚拟电厂为“独立市场主体”&#xff0c;提出硬性目标&#xff1a;2027年全国调节能力≥2000万千瓦&#xff0…...

PHP 8.5 即将发布:管道操作符、强力调试

前不久&#xff0c;PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5&#xff01;作为 PHP 语言的又一次重要迭代&#xff0c;PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是&#xff0c;借助强大的本地开发环境 ServBay&am…...

Python 训练营打卡 Day 47

注意力热力图可视化 在day 46代码的基础上&#xff0c;对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...

Linux部署私有文件管理系统MinIO

最近需要用到一个文件管理服务&#xff0c;但是又不想花钱&#xff0c;所以就想着自己搭建一个&#xff0c;刚好我们用的一个开源框架已经集成了MinIO&#xff0c;所以就选了这个 我这边对文件服务性能要求不是太高&#xff0c;单机版就可以 安装非常简单&#xff0c;几个命令就…...