LeetCode上的题目416：Partition Equal Subset Sum（分割等和子集）
发布时间
阅读量：
阅读量
【针对这一问题，我们可首先对集合中的元素进行累加运算，从而获得总和 sum，进而将该问题转换为经典的背包问题形式：
设定一个容量为 sum / 2 的背包，并提供 N 个物品，其中每个物品的重量对应于 nums[i]。现要求判断是否存在一种合理的物品装载方式，使得背包能够被完全填满？
Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
public boolean canPartition(int[] nums) {
int sum = 0;
for(int num : nums) {
sum += num;
}
//若sum为奇数，则一定为false
if(sum % 2 != 0) return false;
//背包容量为sum/2
sum = sum / 2;全部评论 (0)
还没有任何评论哟~