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,
TypeScript:函数类型接口8道大厂指针笔试题让你秒杀指针!!!MySQL 日期时间加减mysql 查询条件之外的数据_mysql 查询符合条件的数据查linux的操作系统版本,如何查看Linux操作系统版本?将String类型转换成Map数据类型使用uuid做MySQL主键,被老板,爆怼一顿C语言中的字符串函数和字符函数linux服务器中毒排查--基础篇C# ASCII码字符转换