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,
uni-app中使用 async + await 实现异步请求同步化Dart中的Isolate十分钟掌握Pytorch搭建神经网络的流程利用python对monkey日志完成自动化分析二进制模2除法(CRC循环冗余检验)vue实现pc端的自适应,rem适配希尔排序Unity面试经验(两天面六家,四个offer,济南)C++实现《走迷宫》小游戏VR、AR和MR这些技术的区别