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

Leetcode 39 组合总和

题意理解:

        一个 无重复元素 的整数数组 candidates 和一个目标整数 target    

        从candidates 取数字,使其和== target ,有多少种组合(candidates 中的 同一个 数字可以 无限制重复被选取

        这道题和之前一道组合的区别:这道题允许重复的数字

解题思路

        组合问题——>递归

        这道题特殊的地方,对组合内数字的和做了要求,而不是个数,一开始并不确定树的深度,组合的大小是不定的。

1.暴力回溯+剪枝优化

class Solution {List<List<Integer>> result=new ArrayList<>();LinkedList<Integer> path=new LinkedList<>();int sum=0;public List<List<Integer>> combinationSum(int[] candidates, int target) {backtracking(candidates,target,0);return result;}public void backtracking(int[] candidates,int target,int index){//结果收集if(sum==target){result.add(new ArrayList<>(path));return;} else if (sum>target) {//剪枝return;}//遍历分支for(int i=index;i<candidates.length;i++){path.add(candidates[i]);sum+=candidates[i];//递归backtracking(candidates,target,i);//回溯path.removeLast();sum-=candidates[i];}}
}

2.分析

时间复杂度:O(n\times 2^{n})

        n个位置,每个位置有两种可能选或不选。

        时间复杂度和树的深度有关,是所有可行解之和

空间复杂度:O(n)

相关文章:

Leetcode 39 组合总和

题意理解&#xff1a; 一个 无重复元素 的整数数组 candidates 和一个目标整数 target 从candidates 取数字&#xff0c;使其和 target &#xff0c;有多少种组合&#xff08;candidates 中的 同一个 数字可以 无限制重复被选取&#xff09; 这道题和之前一道组合的区别&am…...

Windows下使用AndroidStudio及CMake编译Android可执行程序或静态库动态库

Windows下使用AndroidStudio及CMake编译Android可执行程序或静态库动态库 文章目录 Windows下使用AndroidStudio及CMake编译Android可执行程序或静态库动态库一、前言二、编译环境三、示例C/CPP程序1、总体工程结构2、示例代码3、CMakeLists.txt&#xff08;重要&#xff09;4、…...

MySQL七 | 存储引擎

目录 存储引擎 存储引擎特点 存储引擎选择 Innodb与MyISAM区别 存储引擎 默认存储引擎:InnoDB show engines;#展示当前数据库支持的存储引擎 存储引擎特点 特点InnoDBMyISAMMemory存储限制64TB有有事务安全支持--锁机制行锁表锁表锁Btree锁支持支持 支持 Hash索引--支…...

网上下载的pdf文件,为什么不能复制文字?

不知道大家有没有到过这种情况&#xff1f;在网上下载的PDF文件打开之后&#xff0c;发现选中文字之后无法复制。甚至其他功能也都无法使用&#xff0c;这是怎么回事&#xff1f;该怎么办&#xff1f; 当我们发现文件打开之后&#xff0c;编辑功能无法使用&#xff0c;很可能是…...

Linux下apisix离线安装教程

Linux下apisix离线安装教程 一、首先需要安装etcd&#xff1a;二、通过rpm离线安装apisix三、启动apisix四、安装apisix-dashboard1、安装2、更改dashboard登录账号名和密码3、运行 一、首先需要安装etcd&#xff1a; 解压缩etcd后执行以下命令&#xff1a; tar -xvf etcd-v3.…...

基于STM32 + DMA介绍,应用和步骤详解(ADC多通道)

前言 本篇博客主要学习了解DMA的工作原理和部分寄存器解析&#xff0c;针对ADC多通道来对代码部分&#xff0c;应用部分作详细讲解&#xff0c;掌握代码编程原理。本篇博客大部分是自己收集和整理&#xff0c;如有侵权请联系我删除。 本次博客开发板使用的是正点原子精英版&am…...

openGauss学习笔记-144 openGauss 数据库运维-例行维护-慢sql诊断

文章目录 openGauss学习笔记-144 openGauss 数据库运维-例行维护-慢sql诊断144.1 背景信息144.2 前提条件 openGauss学习笔记-144 openGauss 数据库运维-例行维护-慢sql诊断 144.1 背景信息 在SQL语句执行性能不符合预期时&#xff0c;可以查看SQL语句执行信息&#xff0c;便…...

计算机毕业设计springboot+ssm停车场车位预约系统java

管理员不可以注册账号 停车位包括车位所在楼层、车位编号、车位类型(全时间开放/高峰期开放)、预定状态等 用户预约时要求支付预约时间段的停车费用 违规行为&#xff1a;1.停车超过预约时间段 2.预约未使用 于系统的基本要求 &#xff08;1&#xff09;功能要求&am…...

打破常规思维:Scrapy处理豆瓣视频下载的方式

概述 Scrapy是一个强大的Python爬虫框架&#xff0c;它可以帮助我们快速地开发和部署各种类型的爬虫项目。Scrapy提供了许多方便的功能&#xff0c;例如请求调度、数据提取、数据存储、中间件、管道、信号等&#xff0c;让我们可以专注于业务逻辑&#xff0c;而不用担心底层的…...

系列学习前端之第 2 章:一文精通 HTML

全套学习 HTMLCSSJavaScript 代码和笔记请下载网盘的资料&#xff1a; 链接: https://pan.baidu.com/s/1-vY2anBdrsBSwDZfALZ6FQ 提取码: 6666 HTML 全称&#xff1a;HyperText Markup Language&#xff08;超文本标记语言&#xff09; 1、 HTML 标签 1. 标签又称元素&#…...

SCSS Module 这样处理配置和使用太赞了

SCSS Module 只是Scss和Css Module结合&#xff0c;可以利用SCSS对代码静态处理的能力&#xff0c;使得样式处理更强大一些&#xff0c;并不是什么新的东西&#xff0c;对比css-in-js和scoped&#xff0c;个人偏向喜欢Scss Module做样式隔离&#xff0c;先说一下优点&#xff1…...

【Unity动画】Unity 2D动画创建流程

本文以2D为案例&#xff0c;讲解Unity 播放动画的流程 准备和导入2D动画资源 外部导入序列帧生成的 Unity内部制作的 外部导入的3D动画 2.创建动画过程 打开时间轴Ctrl6 选中场景中的一个未来需要播放动画的物体 回到时间轴点击Create一个新动画片段 拖动2D动画资源放入…...

【算法每日一练]-图论(保姆级教程篇12 tarjan篇)#POJ3352道路建设 #POJ2553图的底部 #POJ1236校园网络 #缩点

目录&#xff1a; 今天知识点 加边使得无向图图变成双连通图 找出度为0的强连通分量 加边使得有向图变成强连通图 将有向图转成DAG图进行dp POJ3352&#xff1a;道路建设 思路&#xff1a; POJ2553&#xff1a;图的底部 思路&#xff1a; POJ1236校园网络 思路&#x…...

Python数据科学视频讲解:数据挖掘与建模的注意事项

1.7 数据挖掘与建模的注意事项 视频为《Python数据科学应用从入门到精通》张甜 杨维忠 清华大学出版社一书的随书赠送视频讲解1.7节内容。本书已正式出版上市&#xff0c;当当、京东、淘宝等平台热销中&#xff0c;搜索书名即可。内容涵盖数据科学应用的全流程&#xff0c;包括…...

unity | 动画模块之循环滚动选项框

一、作者的话 评论区有人问&#xff0c;有没有竖排循环轮播选项框&#xff0c;我就写了一个 二、效果动画 如果不是你们想要的&#xff0c;就省的你们继续往下看了 三、制作思路 把移动分成里面的方块&#xff0c;还有背景&#xff08;父物体&#xff09;&#xff0c;方块自…...

TinyMPC - CMU (卡耐基梅隆大学)开源的机器人 MPC 控制器

系列文章目录 CasADi - 最优控制开源 Python/MATLAB 库 文章目录 系列文章目录前言一、机器人硬件对比1.1 Teensy 上的微控制器基准测试1.2 机器人硬件1.3 BibTeX 二、求解器三、功能&#xff08;预期&#xff09;3.1 高效3.2 鲁棒3.3 可嵌入式3.4 最小依赖性3.5 高效热启动3.…...

C++ 对象的初始化和清理:构造函数和析构函数

目录 构造函数和析构函数 构造函数 析构函数 构造函数的分类及调用 括号法 显示法 隐式转换法 拷贝构造函数的调用时机 使用一个已经创建完毕的对象来初始化一个新对象 值传递的方式给函数参数传值 以值方式返回局部对象 构造函数调用规则 初始化列表 类对象作…...

Tmux中使用Docker报错 - 解决方案

问题 进入Tmux会话后&#xff0c;在其中使用Docker可能会出现如下报错&#xff1a; Got permission denied while trying to connect to the Docker ……解决方案 退出tmux会话: tmux detach在tmux会话外部杀掉tmux进程&#xff1a; pkill -f tmux重新进入tmux&#xff1a…...

如何在WordPress中批量替换图片路径?

很多站长在使用WordPress博客或者搬家时&#xff0c;需要把WordPress文章中的图片路径进行替换来解决图片不显示的问题。总结一下WordPress图片路径批量替换的过程&#xff0c;方便有此类需求的站长们学习。 什么情况下批量替换图片路径 1、更换了网站域名 有许多网站建设初期…...

el-pagination 纯前端分页

需求&#xff1a;后端把所有数据都返给前端&#xff0c;前端进行分页渲染。 实现思路&#xff1a;先把数据存储到一个大数组中&#xff0c;然后调用方法进行切割。主要使用数组的slice方法 所有代码&#xff1a; html <template><div style"padding: 20px&qu…...

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

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

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

基础测试工具使用经验

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

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

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

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

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...