leetcode416.分割等和子集
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相当。示例 1：
<strong>输入：</strong>nums =
<strong>输出：</strong>true
<strong>解释：</strong>数组可以分割成 和 。 示例 2：
<strong>输入：</strong>nums =
<strong>输出：</strong>false
<strong>解释：</strong>数组不能分割成两个元素和相等的子集。
提示：
[*]1 <= nums.length <= 200
[*]1 <= nums <= 100
思路：类似leetcode139.单词拆分-CSDN博客，假如数组和为奇数，则一定无法分割；假如为偶数，则转换为背包是否能装满题目，dp表示容量j是否能凑成
public boolean canPartition(int[] nums) {
int sum=0;
for(int i=0;i<nums.length;i++)
sum+=nums;
// 如果是奇数，一定无法分割
if(sum%2!=0)
return false;
// 如果是偶数，则转换为背包是否能装满问题，dp表示容量j是否能凑成
boolean [] dp=new boolean;
dp=true;
for(int i=0;i<nums.length;i++){
//为保证每个物品用一次，从后往前遍历背包！！
for(int j=dp.length-1;j>=0;j--){
if(dp&&j+nums<dp.length){
dp]=true;
if(j+nums==dp.length-1)
return true;
}
}
}
return false;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]