leetcode416.分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相当。
示例 1：

1. <strong>输入：</strong>nums = [1,5,11,5]
2. <strong>输出：</strong>true
3. <strong>解释：</strong>数组可以分割成 [1, 5, 5] 和 [11] 。

复制代码

示例 2：

1. <strong>输入：</strong>nums = [1,2,3,5]
2. <strong>输出：</strong>false
3. <strong>解释：</strong>数组不能分割成两个元素和相等的子集。

复制代码

提示：

• 1 <= nums.length <= 200
  
• 1 <= nums <= 100
  

思路：类似leetcode139.单词拆分-CSDN博客，假如数组和为奇数，则一定无法分割；假如为偶数，则转换为背包是否能装满题目，dp[j]表示容量j是否能凑成

1. public boolean canPartition(int[] nums) {
2.         int sum=0;
3.         for(int i=0;i<nums.length;i++)
4.             sum+=nums[i];
5.         // 如果是奇数，一定无法分割
6.         if(sum%2!=0)
7.             return false;
8.         // 如果是偶数，则转换为背包是否能装满问题，dp[j]表示容量j是否能凑成
9.         boolean [] dp=new boolean[sum/2+1];
10.         dp[0]=true;
11.         for(int i=0;i<nums.length;i++){
12.             //为保证每个物品用一次，从后往前遍历背包！！
13.             for(int j=dp.length-1;j>=0;j--){
14.                 if(dp[j]&&j+nums[i]<dp.length){
15.                     dp[j+nums[i]]=true;
16.                     if(j+nums[i]==dp.length-1)
17.                         return true;
18.                 }
19.             }
20.         }
21.         return false;
22.     }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。