代码随想录算法训练营第35天 | 416.分割等和子集
代码随想录算法训练营第35天 | 416.分割等和子集
文章目录
- 代码随想录算法训练营第35天 | 416.分割等和子集
- 416.分割等和子集
- 解题思路
- 代码实现
- 题目总结
416.分割等和子集
题目链接：416.分割等和子集
解题思路
只要集合中出现 sum/2 的子集总和，那么这个数组就可以分割成两个相同元素的子集。本题可以使用回溯算法暴力搜索出所有答案，但是很费时，考虑将本题转换为背包问题解决。因为元素只能使用一次，所有是0-1背包。
- 确定dp数组及下标的含义：dp[j] 表示容量是 j 的背包最大可以凑成的总和
- 确定递推公式：dp[j]=max(dp[j],dp[j-nums[i]]+nums[i])
- 初始化dp数组：题中给出的价值都是正整数，那么非0下标的数组都初始化为0即可
- 确定遍历顺序：一维dp数组，遍历物品的 for 循环在外层，遍历背包的 for 循环在内层，且内层 for 循环使用倒叙遍历
- 举例推导dp数组
代码实现
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
vector<int> dp(10001, 0);
for (int i = 0; i < nums.size(); i++) {
sum += nums[i];
}
if (sum % 2 == 1)
return false;
int target = sum / 2;
for (int i = 0; i < nums.size(); i++) {
for (int j = target; j >= nums[i]; j--) {
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
}
}
if (dp[target] == target)
return true;
return false;
}
};
题目总结
本题是一道0-1背包应用类的题目，需要拆解题目，套用0-1背包的场景。