LeetCode_ 416_ Divide equal sum subsets

Topic link

• https://leetcode.cn/problems/partition-equal-subset-sum/

Title Description

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

Their thinking

Dynamic programming

• The volume of the backpack is sum/2
• Goods to be put in the backpack （ The elements in the set ) The weight is the value of the element , Value is also the value of the element
• If the backpack is just full , Indicates that the sum of sum/2 Subset
• Every element in the backpack cannot be put in repeatedly

Dynamic programming five steps

• determine dp The meaning of array and subscript
  • dp[j]: Capacity of j The backpack , The maximum can be made up j The sum of the subsets of is dp[j]
• Determine the recurrence formula
  • stay 01 In the backpack , The recurrence formula is dp[j] = Math.max(dp[j],dp[j-weight[i] + value[i]]),dp[j] = Math.max(dp[j],dp[j-nums[i]] + nums[i])
• dp Array initialization
  • dp[0] = 0, Other subscripts dp[i] = 0
• Determine the traversal order
  • Traversal of items for Loop on the outer layer , Traversing the backpack for Loop on the inner layer , And inner for Loop backward traversal
• For example, push to dp Array
  • If dp[j] == j, It means that the sum of subsets in the set can just be summed up j

AC Code

class Solution {
    
    public boolean canPartition(int[] nums) {
    
        int sum = 0;
        for (int i : nums) {
    
            sum += i;
        }
        if (sum % 2 != 0) {
    
            return false;
        }
        int bagWeight = sum / 2;
        int[] dp = new int[bagWeight + 1];
        dp[0] = 0;
        for (int i = 0; i < nums.length; i++) {
    
            for (int j = bagWeight; j >= nums[i]; j--) {
    
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        return dp[bagWeight] == bagWeight;
    }
}