LeetCode 416. 分割等和子集 JAVA 背包问题

冷不防 2022-12-13 12:56 147阅读 0赞

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。  
注意:  
每个数组中的元素不会超过 100  
数组的大小不会超过 200

示例 1:
    
    输入: [1, 5, 11, 5]
    
    输出: true
    
    解释: 数组可以分割成 [1, 5, 5] 和 [11].
     
    
    示例 2:
    
    输入: [1, 2, 3, 5]
    
    输出: false
    
    解释: 数组不能分割成两个元素和相等的子集.
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/partition-equal-subset-sum
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：  
1、计算出数组和  
2、如果数组和为奇数，而一定不能分割为等和；如果数组和为偶数，则求出其一半sum为多少  
3、接下来就是背包问题了，设置dp\[sum+1\],且dp\[0\]=true,

此处为主要代码，第一层循环是遍历nums数组，第二层遍历是找出所有数字组成的和可以达到那些个数，这里0-j是数组任意组合可以达到的和，注意的点就是j必须sum，从后往前遍历，如果从前往后遍历的话，假设nums\[i\]=1的话，在第二层循环中,则随着循环,因为dp\[0\]=true,所以dp\[1\]=true;接着因为dp\[1\]=true,所以dp\[2\]=true;······因为dp\[sum-1\]=true,所以dp\[sum\]=true;所以最终结果一定会是正确，所以一定要从后往前遍历。

for(int i=0;i<nums.length;i++)
            {
        
                for(int j=sum;j>=nums[i];j--)
                {
        
                    if(tmp[j-nums[i]]) tmp[j]=true;
                }
            }

class Solution {
        
        public boolean canPartition(int[] nums) {
        
            if(nums.length<1) return false;
            int sum=0;
            for(int i=0;i<nums.length;i++) sum+=nums[i];
            if(sum%2==1) return false;
            else sum/=2;
            boolean tmp[]=new boolean[sum+1];
            tmp[0]=true;
            for(int i=0;i<nums.length;i++)
            {
        
                for(int j=sum;j>=nums[i];j--)
                {
        
                    if(tmp[j-nums[i]]) tmp[j]=true;
                }
            }
            return tmp[sum];
        }
    }