Leetcode 416.分割等和子集
2024-09-05 14:22:18
分割等和子集
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
注意:
- 每个数组中的元素不会超过 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 sum=0;
for(int num:nums){
sum+=num;
}
if((sum&1)==1) return false;
sum>>=1;
boolean[] dp=new boolean[sum+1];
dp[0]=true;
for(int j=0;j<nums.length;j++){
for(int i=sum;i>=nums[j];i--){
dp[i]=dp[i]||dp[i-nums[j]];
}
if(dp[sum]){
return true;
}
}
return dp[sum];
}
}
最新文章
- .NET Core全面扫盲贴
- [转] 擎天哥as3教程系列第二回——性能优化
- ssential Diagram for Windows FormsC#/winForm类似visio的拓扑图节点连线控件免费下载
- Android IOS WebRTC 音视频开发总结(七十)-- 移动端音视频技术优化的七个方向
- 【BZOJ】1027: [JSOI2007]合金(凸包+floyd)
- WebService 的一些基本概念
- tomcat 下虚拟机部署导致应用filter失效的问题
- npm和gulp学习笔记
- secedit
- Andy Williams 《Love Story》
- Jmeter之性能测试插件PerfMon Metrics Collector监听器,实时监听服务器资源(十四)
- UNIX网络编程——TCP—经受时延与nagle算法、滑动窗口、拥塞窗口
- 2015年CSDN博客排名第一名,何方神圣?
- ES6的let
- ZZW_shell脚本中的调用MYSQL传参及注意的问题
- MFC停靠窗口实现(CDockablePane)
- leetcode — two-sum-ii-input-array-is-sorted
- nginx 301 302跳转配置总结
- TCP传输协议
- 【JavaScript 从零开始】 原始值和对象引用、类型转换
热门文章
- SPEC CPU 使用简介
- Android 贝塞尔曲线的浅析
- log4cxx安装使用
- (转)VC得到可用的串口列表
- [LR]遇到的坑及常用技巧
- connect() to 192.168.30.71:8082 failed (99: Cannot assign requested address) while connecting to upstream, client: 114.80.182.136, server: localhost, request: ";GET /home/senior HTTP/1.1";, upstream: ";
- 如何给SAP Cloud Connector Region列表中添加新的Region
- 使用JS的画布制作一个瞄准镜
- tomcat - 自带日志的区分
- 课下作业04-2String的使用方法