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

力扣题解(组合总和IV)

377. 组合总和 Ⅳ

给你一个由 不同 整数组成的数组 nums ,和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

思路:

本题实质上是给一些数字,让他们在满足和是target的情况下随机排列组合,然后返回所有的排列数目。注意,本题和完全背包问题有所不同,完全背包问题不要求有先后顺序的区别,比如先放第i个物品再放第一个物品和先放第一个物品再放第二个物品没有区别,但是本题例如1+3=4和3+1=4就是不一样,因此dp数组的含义,具体做法有所不同。

dp[i]表示和是i的所有组合数目。dp[i]+=dp[i-nums[i]]。(对于可以视为在和是i-nums[i]的所有排列方法后面加一个nums[i],注意我的说法,是在所有组合的后面,是后面而不是任意位置,这一点接下来会用到!)

对于循环,本题外层循环是i从0到target,内层循环是对nums数组的遍历。本题外层循环个人理解方式是规定目前最后进入的元素该是那个,然后内存循环表示要进nums[i],这样就可以实现每次遍历都在对应的上一个外层循环排序后加一个元素,保证了没有重复。这里不太好说明,就比如假如有数字1,2,3,第一次会有三个式子1=1,2=2,3=3.然后第二次大循环会有1+1=2,1+2=3,1+3=4,2+1=3,2+2=4,2+3=5,3+1=4,3+2=5,3+3=6,可以很明显看出除了最后一个元素外的前面那一串式子就是上一次外层循环得到的所有式子。(即1,2,3)

初始化:

dp[0]=1,因为一个元素都没有才能使得和为0,只有一种组合。

注意:本题所有排列组合数目可能会非常大,因此通过模运算来保证不会超出int存储范围。

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {const int mod=1e10;int n=nums.size();vector<long long>dp(target+1,0);dp[0]=1;for(int j=0;j<=target;j++){for(int i=0;i<n;i++){  if(j-nums[i]>=0)dp[j]+=dp[j-nums[i]];dp[j]%=mod;}}return dp[target];}
};

相关文章:

力扣题解(组合总和IV)

377. 组合总和 Ⅳ 给你一个由 不同 整数组成的数组 nums &#xff0c;和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。 题目数据保证答案符合 32 位整数范围。 思路&#xff1a; 本题实质上是给一些数字&#xff0c;让他们在满足和是targ…...

Postgresql主键自增的方法

Postgresql主键自增的方法 一.方法&#xff08;一&#xff09; 使用 serial PRIMARY KEY 插入数据 二.方法&#xff08;二&#xff09; &#x1f388;边走、边悟&#x1f388;迟早会好 一.方法&#xff08;一&#xff09; 使用 serial PRIMARY KEY 建表语句如下&#xf…...

【源码阅读】Sony的go breaker熔断器源码探究

文章目录 背景源码分析总结 背景 在微服务时代&#xff0c;服务和服务之间调用、跨部门调用都是很常见的事&#xff0c;但这些调用都存在很多不确定因素&#xff0c;如核心服务A依赖的部门B服务挂掉了&#xff0c;那么A本身的功能将会受到直接的影响&#xff0c;而这些都会影响…...

LeetCode题(66,69,35,88)--《c++》

66.加一 // // Created by wxj05 on 2024/7/20. // //法一 class Solution { public:vector<int> plusOne(vector<int>& digits) {bool carry true; // 进位标志for (int i digits.size() - 1; i > 0 && carry; --i) {digits[i] 1;carry digit…...

来参与“向日葵杯”全国教育仿真技术大赛~

可点击进行了解&#xff1a;“向日葵杯”全国教育仿真技术大赛 (sunmooc.cn) 本次大赛共分为四个赛道&#xff1a;自主命题赛道、教育知识图谱设计赛道、FPGA硬件扑克牌对抗赛道、EasyAR元宇宙空间设计赛道。 参赛对象 &#xff1a; 具有正式学籍的在校研究生&#xff0c;本科…...

SQL每日一题:删除重复电子邮箱

题干 表: Person -------------------- | Column Name | Type | -------------------- | id | int | | email | varchar | -------------------- id 是该表的主键列(具有唯一值的列)。 该表的每一行包含一封电子邮件。电子邮件将不包含大写字母。 编写解决方案 删除 所有重复…...

3、宠物商店智能合约实战(truffle智能合约项目实战)

3、宠物商店智能合约实战&#xff08;truffle智能合约项目实战&#xff09; 1-宠物商店环境搭建、运行2-webjs与宠物逻辑实现3-领养智能合约初始化4-宠物领养实现5-更新宠物领养状态 1-宠物商店环境搭建、运行 https://www.trufflesuite.com/boxes/pet-shop 这个还是不行 或者…...

数据库系列

目录 一、数据库的概念和作用 1.数据库的特点 2.数据模型 二、数据库系统 1.数据库管理系统 2.数据库的基本操作 一、数据库的概念和作用 数据库是指长期存储在计算机内&#xff0c;有组织的、可共享的数据集合。它可视为一个电子化的文件柜&#xff0c;用来存储电子文件…...

极狐GitLab如何启用和配置PlantUML?

GitLab 是一个全球知名的一体化 DevOps 平台&#xff0c;很多人都通过私有化部署 GitLab 来进行源代码托管。极狐GitLab &#xff1a;https://gitlab.cn/install?channelcontent&utm_sourcecsdn 是 GitLab 在中国的发行版&#xff0c;专门为中国程序员服务。可以一键式部署…...

Shell 构建flutter + Android 生成Apk

具体步骤 #shell 具体实现和说明如下: echo "build_start_apk!" echo "编译此脚本的前提条件如下:" #在Android 项目的主工程下,进入主工程文件夹,创建build-android 文件夹,在其文件夹下有build-android.sh文件,此文件就是整个文章的脚本内容(…...

如何用手机压缩视频?手机压缩视频方法来了

高清视频的大文件大小常常成为分享和存储的障碍&#xff0c;尤其是在数据流量有限或存储空间紧张的情况下。幸运的是&#xff0c;无论是智能手机还是个人电脑&#xff0c;都有多种方法可以帮助我们轻松压缩视频文件&#xff0c;以适应不同的需求和情境。本文将介绍如何在手机上…...

Linux下如何安装配置Elastic Stack日志收集系统

安装和配置Elastic Stack日志收集系统&#xff0c;包括Elasticsearch、Logstash和Kibana&#xff0c;是一个相对复杂的过程。本篇文章将逐步引导您完成整个过程。 安装Java Elasticsearch、Logstash和Kibana都需要Java运行环境。首先&#xff0c;您需要在Linux系统上安装Java…...

【深入C++】map和set的使用

文章目录 C 中的容器分类1. 顺序容器2. 关联容器3. 无序容器4. 容器适配器5. 字符串容器6. 特殊容器 set1.构造函数2.迭代器3.容量相关的成员函数4.修改器类的成员函数5.容器相关操作的成员函数 multiset1.equal_range map1.初始化相关的函数2.迭代器3.容量相关的成员函数4.访问…...

跟代码执行流程,读Megatron源码(二)训练入口pretrain_gpt.py

Megatron-LM默认支持GPT、T5、BERT等多个常见模型的预训练&#xff0c;当下大模型流行&#xff0c;故以pretrain_gpt.py为例做源码的走读。 一. 启动pretrain_gpt.py pretrain_gpt.py为GPT类模型的训练入口&#xff0c;它通过命令行形式被调用&#xff0c;其精确执行路径位于M…...

MATLAB练习题——矩阵(2)

逻辑运算 a [5 0.2 0 -8 -0.7 ]&#xff0c;在进行逻辑运算时&#xff0c;a 相当于什么样的逻辑量。 相当于 a[1 1 0 1 1] 角度运算 在 sin(x)运算中&#xff0c;x 是角度还是弧度&#xff1f; 在 sin(x)运算中&#xff0c;x 是弧度&#xff0c;MATLAB 规定所有…...

arm、AArch64、x86、amd64、x86_64 的区别

arm vs AArch64 vs amd64 vs x86_64 vs x86 的区别 当涉及到 CPU 的时候&#xff0c;有许多术语&#xff1a;AArch64、x86_64、amd64、arm 等等。了解它们是什么以及它们之间的区别。 当你查看数据表或软件下载页面时是否被 ARM、AArch64、x86_64、i386 等术语混淆&#xff1f;…...

【SpringBoot】 jasypt配置文件密码加解密

目前我们对yml配置文件中的密码都是明文显示&#xff0c;显然这不安全&#xff0c;有的程序员离职了以后可能会做一些非法骚操作&#xff0c;所以我们最好要做一个加密&#xff0c;只能让领导架构师或者技术经理知道这个密码。所以这节课就需要来实现一下。 我们可以使用jasypt…...

复杂网络的任意子节点的网络最短距离

复杂网络的任意子节点的网络最短距离 题目要求介绍 本文算法测试用的数据集为空手道俱乐部&#xff0c;其中空手道俱乐部的数据集可通过这个链接进行下载•http://vlado.fmf.uni-lj.si/pub/networks/data/Ucinet/UciData.htm#zachary 摘要 本文旨在解决复杂网络中任意子节点…...

(Qt) 文件读写基础

文章目录 &#x1f5c2;️前言&#x1f4c4;ref&#x1f4c4;访问标记&#x1f5c3;️enum 标记 &#x1f5c2;️Code&#x1f4c4;demo&#x1f4c4;分点讲解&#x1f5c3;️继承体系&#x1f5c3;️打开/关闭&#x1f5c3;️写&#x1f5c3;️读 &#x1f5c2;️END&#x1f…...

全产业布局对穿戴甲品牌连锁店的意义

对于美甲行业来说&#xff0c;穿戴甲虽然不是什么新生事物&#xff0c;但也就是近两年才流行开来。面对井喷的市场需求&#xff0c;相应的从业者&#xff0c;不管是品牌连锁店&#xff0c;还是做批发、外贸&#xff0c;美甲周边、亦或是OEM的&#xff0c;大家都忙得不亦乐乎&am…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

AI病理诊断七剑下天山,医疗未来触手可及

一、病理诊断困局&#xff1a;刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断"&#xff0c;医生需通过显微镜观察组织切片&#xff0c;在细胞迷宫中捕捉癌变信号。某省病理质控报告显示&#xff0c;基层医院误诊率达12%-15%&#xff0c;专家会诊…...

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录Webhook 2 API文档说明 点击设置说明 查看自…...

云原生周刊:k0s 成为 CNCF 沙箱项目

开源项目推荐 HAMi HAMi&#xff08;原名 k8s‑vGPU‑scheduler&#xff09;是一款 CNCF Sandbox 级别的开源 K8s 中间件&#xff0c;通过虚拟化 GPU/NPU 等异构设备并支持内存、计算核心时间片隔离及共享调度&#xff0c;为容器提供统一接口&#xff0c;实现细粒度资源配额…...

从物理机到云原生:全面解析计算虚拟化技术的演进与应用

前言&#xff1a;我的虚拟化技术探索之旅 我最早接触"虚拟机"的概念是从Java开始的——JVM&#xff08;Java Virtual Machine&#xff09;让"一次编写&#xff0c;到处运行"成为可能。这个软件层面的虚拟化让我着迷&#xff0c;但直到后来接触VMware和Doc…...