力扣416分割等和子集

变相的0-1背包问题

class Solution {
    public boolean canPartition(int[] nums) {
        //两个元素和相等，意味着有一个子集的和为sum的一半
        //如果sum是奇数，肯定是false,如果max 大于sum/2肯定也是false
       //dp[i][j]维度是 nums.length，和sum/2+1，其意思就是在下标[0,i]这个区间里的所有整数，在它们当中是否能够选出一些数，使得这些数之和为j
       int sum=0;
       int max=Integer.MIN_VALUE;
       for(int i=0;i<nums.length;i++){
           sum+=nums[i];
           max=Math.max(max,nums[i]);
       }
       if(sum%2!=0) return false;
       if(max>sum/2) return false; 
       int target=sum/2;
       boolean[][] dp=new boolean[nums.length][target+1];
       boolean a=false;
       boolean b=false;
       for(int l=0;l<target+1;l++){
           if(nums[0]==l) dp[0][l]=true;
       }
       for(int i=1;i<nums.length;i++){
           for(int j=0;j<target+1;j++){
           //不选择nums[i]
            a=dp[i-1][j];
           //选择nums[i]
            if(nums[i]==j) b=true;
            else if(nums[i]<j) b=dp[i-1][j-nums[i]];
            //两种情况只要一种满足就行
            dp[i][j]=a||b;
       }
       }
       return dp[nums.length-1][target];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34