416.分割等和子集

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

注意:

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

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

示例 2:

输入:
[1, 2, 3, 5]
输出:
false
解释: 数组不能分割成两个元素和相等的子集.

思路:

先判断总数是否是偶数,确定背包容量,然后遍历判断背包容量是否够大,不够大当前状态则取决于上一个状态,够大则将背包容量减少,即将该元素放入背包中,再判断状态。

代码:
class Solution { public: bool canPartition(vector<int> &nums) { int tar = 0, n
= nums.size(); for (int i = 0; i < n; i++) tar += nums[i]; if (tar % 2 != 0)
//判断总和是否是偶数 return false; tar /= 2; //每个子集的和 vector<bool> dp(tar + 1, false); dp
[0] = true; //database for (int i = 0; i < n; i++) { for (int j = tar; j >= 0; j
--) //反向遍历,保证每个元素只使用一次 { if (j - nums[i] >= 0) { dp[j] = dp[j] || dp[j - nums[i]
]; } } } return dp[tar]; } };

技术
©2019-2020 Toolsou All rights reserved,
中国移动科普:为什么手机移动网络要叫 “蜂窝移动网络”C语言---------俄罗斯方块(源代码)javascript事件(零基础详解)python实现vlookup_干货一:怎么在python里面实现vlookupC语言中数据的存储List集合中的常见面试题以及简单思路第十一届蓝桥杯python大学组国赛真题计算机科班出身和培训出身有什么区别?Java开发2020年最新常见面试题整理仿抖音小球刷新进度条(两个小球转动),代码很简单