Daily question - split equal sum subset

416. To divide into equal and subsets

Steal or not

416. To divide into equal and subsets
To give you one Contains only positive integers Of Non empty Array nums . Please decide whether you can divide this array into two subsets , Make the sum of the elements of the two subsets equal .

Example 1：

Input ：nums = [1,5,11,5]
Output ：true
explain ： Arrays can be divided into [1, 5, 5] and [11] .
Example 2：

Input ：nums = [1,2,3,5]
Output ：false
explain ： An array cannot be divided into two elements and equal subsets .

Tips ：

1 <= nums.length <= 200
1 <= nums[i] <= 100

Ideas

The problem is 01 knapsack , Can divide equally , It must be divisible 2, Otherwise directly false

Finally, the numbers are accumulated , Add up and divide half , See if half the capacity can be filled , If it can be full , It can be explained that it can be divided , Otherwise, it's impossible .

dp[j] Represents the accumulation of backpack capacity （ Can steal ） The maximum of

The outermost cycle represents the number of items that can be stolen

Except one line , Each space represents the maximum value of the corresponding weight of the item that can be stolen

goods [1,5,11,5]

weight	11	10	9	8	7	6	5	4	3	2	1	0
goods 1	1	1	1	1	1	1	1	1	1	1	1	0
goods 2	6	6	6	6	6	6	5	1	1	1	1	0
goods 3	Can't steal keep 6	6	6	6	6	6	5	1	1	1	1	0
goods 4	11	10	6	6	6	6	5	1	1	1	1	0

If the weight grows from small to large , Will evolve into multiple backpacks , An item will be put repeatedly

 for (int j =0; j>=nums[i]&&j<=weight; j++) {
    

      dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);

}

weight	0	1	2	3	4	5	6	7	8	9	10	11
goods 1	0	1	2	3	4	5	6	7	8	9	10	11
goods 2	0	1	2	3	4	5	7
goods 3
goods 4

The title algorithm code is as follows

public class  To divide into equal and subsets  {
    
    public boolean canPartition(int[] nums) {
    
        if (nums.length==0||nums==null){
    
            return false;
        }
        int sum=0;
        for (int num : nums) {
    
            sum+=num;
        }
        if (sum%2!=0){
    
            return false;
        }
        int weight =sum/2;
        int dp[]=new int[weight+1];
        // Items inside 
        for (int i = 0; i < nums.length; i++) {
    
            for (int j =weight; j>=nums[i]; j--) {
    
                // Don't steal dp[j]  steal dp[j-nums[i]]+nums[i]
                dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        return dp[weight]==weight;
    }
}