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

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

【Java学习笔记】Arrays类

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

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

1.3 VSCode安装与环境配置

进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件&#xff0c;然后打开终端&#xff0c;进入下载文件夹&#xff0c;键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分

一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计&#xff0c;提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合&#xff1a;各模块职责清晰&#xff0c;便于独立开发…...