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

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

大数据零基础学习day1之环境准备和大数据初步理解

学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 &#xff08;1&#xff09;设置网关 打开VMware虚拟机&#xff0c;点击编辑…...

Axios请求超时重发机制

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

C++.OpenGL (14/64)多光源(Multiple Lights)

多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...

LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》

这段 Python 代码是一个完整的 知识库数据库操作模块&#xff0c;用于对本地知识库系统中的知识库进行增删改查&#xff08;CRUD&#xff09;操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 &#x1f4d8; 一、整体功能概述 该模块…...

【Linux】Linux 系统默认的目录及作用说明

博主介绍&#xff1a;✌全网粉丝23W&#xff0c;CSDN博客专家、Java领域优质创作者&#xff0c;掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围&#xff1a;SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...

Windows安装Miniconda

一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...