首页 > 代码库 > 平分区间

平分区间

题目:就是从一个数组中找出一些数,使得这些数的和等于剩下没被找的数的和

思路:实际上就是找一些数,使他们的和等于数组总和的一半,,所以这是一道01背包的变形题,对于每个数字,要么选,要么不选即可。

 

 public boolean canPartition(int[] nums) {
        int n=nums.length,sum=0;
        if(n==0) return true;
        for(int i:nums)
            sum+=i;
        if(sum%2==1) return false;
        sum/=2;
        boolean[] dp =new boolean[sum+1];
        dp[0]=true;
        for(int i=1;i<=n;i++){
            for(int j=sum;j>=nums[i-1];j--){
                dp[j]=dp[j]||dp[j-nums[i-1]];
            }
        }
        return dp[sum];
    }

 

平分区间