LeetCode 416. 分割等和子集 做题小结_分割等和子集 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子-程序员宅基地

技术标签: 算法  java  leetcode  动态规划  Leetcode  # 动态规划  数据结构  

题目

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。

注意:

每个数组中的元素不会超过 100
数组的大小不会超过 200
示例 1:

输入: [1, 5, 11, 5]

输出: true

解释: 数组可以分割成 [1, 5, 5] 和 [11].
 

示例 2:

输入: [1, 2, 3, 5]

输出: false

解释: 数组不能分割成两个元素和相等的子集.

代码

class Solution {
    public boolean canPartition(int[] nums) {
		int[] dp = new int[10001];
		int sum=0;
		for(int i=0;i<nums.length;i++) {
			sum+=nums[i];
		}
		int target=sum/2;
		for(int i=0;i<nums.length;i++ ) {
			for(int j=target;j>=nums[i];j--) {
				dp[j]=Math.max(dp[j], dp[j-nums[i]]+nums[i]);
			}
		}
		return sum-dp[target]==target;
    }
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/a12355556/article/details/112972433

智能推荐

在Unity3D中的渲染优化-Drawcall的概念_draw call cpu设置渲染状态-程序员宅基地

文章浏览阅读338次。Draw Call本身的含义很简单,就是CPU调用图像编程接口,如OpenGL中的glDrawElements命令或者DirectX中的DrawIndexedPrimitive命令,以命令GPU进行渲染的操作。一个常见的误区是,Draw Call中造成性能问题的元凶是GPU,认为GPU上的状态切换是耗时的,其实不是的,真正“拖后腿”其实的是CPU。在深入理解Draw Call之前,我们先来看一下CPU和GPU之间的流水线化是怎么实现的,即它们是如何相互独立一起工作的。1.CPU和GPU是如何实现_draw call cpu设置渲染状态

mysql8创建用户并授予权限和移除权限_mysql8授权-程序员宅基地

文章浏览阅读256次。mysql8创建用户并授予所有库的所有权限_mysql8授权

MySQL联合索引与索引下推图文详解_联合索引图解-程序员宅基地

文章浏览阅读3k次,点赞5次,收藏25次。联合索引的树结构、最左匹配原则、如何选择合适的索引列顺序、索引下推图文讲解_联合索引图解

nslookup-程序员宅基地

文章浏览阅读49次。nslookupserver 114.114.114.114set q=mx set q=aset q=ptrset q=ns转载于:https://www.cnblogs.com/huang99882008/p/10696756.html_nslookup时显示的server为114.114.114.114

计算机控制系统的典型类型是什么,计算机控制系统作业参考答案-程序员宅基地

文章浏览阅读2.2k次。计算机控制系统作业参考答案 (15页) 本资源提供全文预览,点击全文预览即可全文预览,如果喜欢文档就下载吧,查找使用更方便哦!9.90 积分计算机控制系统作业参考答案作业一第一章11什么是计算机控制系统画出典型计算机控制系统的方框图。答计算机控制系统又称数字控制系统,是指计算机参与控制的自动控制系统,既用算机代替模拟控制装置,对被控对象进行调节和控制控制系统中的计算机是由硬件和软件两部分组成的硬..._kkxkt

通过广域网(Intelnet)进行远程唤醒[或开机]_magic packet utility-程序员宅基地

文章浏览阅读4k次。WAN远程唤醒与LAN远程唤醒有着诸多不同,WAN远程唤醒首先需要主板、网卡等硬件的支持,需要一条有效的Intelnet连接,与Lan远程唤醒不同的是,WAN远程唤醒需要经过路由器。WAN远程唤醒与LAN远程唤醒有着诸多不同,WAN远程唤醒首先需要主板、网卡等硬件的支持,需要一条有效的Intelnet连接,与Lan远程唤醒不同的是,WAN远程唤醒需要经过路由器,因此下面我就来详细讲解如何在路由_magic packet utility

随便推点

NHibernate *.hbm.xml 文档-程序员宅基地

文章浏览阅读96次。# class<class name="ClassName" (1) table="tableName" (2) discriminator-value="discriminator_value" (3) ...

明明很努力的写博客,为啥没人看?试试这些方法和工具(建议收藏)_csdn发布的博客会有人去看嘛-程序员宅基地

文章浏览阅读2.4k次,点赞38次,收藏84次。知乎高赞:文中列举了互联网一线大厂程序员都在用的工具集合,涉及面非常广,小白和老鸟都可以进来看看,或许有新收获,也希望大家把自己的工具分享在评论区。_csdn发布的博客会有人去看嘛

苹果安卓鸿蒙对比,鸿蒙OS对比iOS,华为再次“超越”,流畅度大幅领先苹果!...-程序员宅基地

文章浏览阅读264次。随着越来越多的细节被曝光,鸿蒙系统也已经进入到了最后内测阶段。近日,华为消费者业务软件部总裁公开王成录表示,华为手机从6月开始,可以陆续升级到鸿蒙系统正式版。这是华为官方首次明确告知正式版推动的时间,此前在2月的Mate X2发布会上,余承东曾宣称会在4月份推动鸿蒙OS。事实上,最近已经有很多用户升级到了鸿蒙系统,不过需要注意的是,现在用户们使用的都是内测版和公测版。前不久,华为刚开启了鸿蒙OS ..._苹果系统,安卓系统,华为鸿蒙系统排名

postgresql upsert 的实现_pqsql upsert-程序员宅基地

文章浏览阅读3.3k次。os: ubuntu 16.04db: postgresql 9.6.8postgresql upsert 是从 9.5 开始引入的功能,语法中并没有 upsert 这个关键字,是通过 insert into 来实现的。所以现在 postgresql 也可以使用 insert into 来实现 oracle 的 merge into 功能。强大,赞一个。语法# su - postgre..._pqsql upsert

计算机网络实验3.1.1·PPP基本配置与分析_ppp的基本配置-程序员宅基地

文章浏览阅读4.8k次,点赞7次,收藏41次。PPP基本配置与分析实验目的实验装置实验原理任务要求实验步骤实验过程实验目的1.掌握 PPP 特点、工作过程和基本配置方法。2.掌握 PPP PAP 鉴别的特点配置方法。3.掌握 PPP CHAP 鉴别的特点和配置方法。4.掌握 PPP IP 地址协商的配置方法。实验装置1.华为 eNSP 软件。2.ping。3.Wireshark。实验原理PPP 是目前使用最为广泛的数据链路层协议,可以在点对点链路上传输多种协议的数据。PPP 包括三个组成部分:1.将数据报封装到串行链路的方法_ppp的基本配置

win7安装sqlserver2014_sqlserver 2014 win7可以安装么-程序员宅基地

文章浏览阅读1.9w次,点赞2次,收藏22次。SQL Server2014要求:https://docs.microsoft.com/zh-cn/sql/sql-server/install/hardware-and-software-requirements-for-installing-sql-server?view=sql-server-2014第一步:下载第二步:解压第三步:管理员身份运行第四步:全新安装..._sqlserver 2014 win7可以安装么

推荐文章

热门文章

相关标签