本文共 631 字,大约阅读时间需要 2 分钟。
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
注意:
- 每个数组中的元素不会超过 100
- 数组的大小不会超过 200
示例 1:
输入: [1, 5, 11, 5]输出: true解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2:
输入: [1, 2, 3, 5]输出: false解释: 数组不能分割成两个元素和相等的子集.
class Solution {
public boolean canPartition(int[] nums) {
if(nums == null) return false;
if(nums.length >200) return false;
int total =0;
for(int i=0; i< nums.length; i++){
if(nums[i] > 100)
return false;
total += nums[i];
}
if(total % 2 != 0) return false;
int avg = total /2;
boolean[] arr = new boolean[total +1];
arr[0] = true;
for(int n: nums){
for(int i = avg; i>= n; i--){
arr[i] = arr[i] || arr[i-n];
}
}
return arr[avg];
}
}
转载地址:https://blog.csdn.net/luxuiary/article/details/106404821 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!