代码随想录算法训练营第 35 天 | LeetCode 416. 分割等和子集

代码随想录算法训练营

Day35 代码随想录算法训练营第 35 天 | LeetCode 416. 分割等和子集

---

---

前言

LeetCode416. 分割等和子集

讲解文档

---

一、LeetCode416. 分割等和子集

1.题目链接

LeetCode416. 分割等和子集

2.思路

（1）为什么能用01背包：每个元素只能用一次
（2）子集是背包----背包最大容量：元素和/2
（元素和如果是偶数，不可能分成两个元素和相等的子集）
（3）物品重量：元素数值；物品价值：元素数值
（4）dp[j] 容量为j时，最大的价值之和
（5）判定两个子集元素和相等：
dp[sum/2]=sum/2
（装不满的情况：dp[7]=6 现在自己里面元素和还没有到sum/2，也就是7，但是剩下的任何元素放进去都会超出容量）

3.题解

class Solution {
public:bool canPartition(vector<int>& nums) {int n = nums.size();// 元素只用一次，说明01背包// dp[i][j]  0-i的范围内 j是容量 dp表示最大价值// 背包最大的容量是sum/2，如果价值为sum/2则说明正好是的自己元素和相等// 元素数值看作物品容量和价值int dp[100001] = {0};int sum = accumulate(nums.begin(), nums.end(), 0);if (sum % 2)return false;int target = sum / 2;for (int i = 0; i < n; i++) {for (int j = target; j >= nums[i]; j--) {dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);}}return dp[target] == target;}
};