Leetcode 416. Split equal sum subset

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

Put the whole collection , Divided into two subsets , Ask if two subsets can and equal
therefore , The capacity of a backpack is the sum of the set / 2, Of course , The capacity must be an integer , So when sum It must not be satisfied when it is an odd number , return false

1. dp[i]： Represents when the capacity is i The largest sum of time
2. because dp[i] There should be two situations ,1 Is to add that the current number does not meet the capacity i So no more numbers ,2 Yes, plus the current number, it still meets the capacity i, therefore dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
3. initialization ： Because when the capacity is 0 The maximum capacity is also 0, Array has no negative value , Don't worry about initial value overrides dp value , So all are initialized to 0 that will do
4. traversal order ： from 2 The recursion formula of can get the first traversal of the article , Post traversal capacity , And because it's 0-1 knapsack , One dimensional scrolling array , So the capacity is traversed from back to front

Code

class Solution {
    
public:
    // 1.  All sums can be divided into two sets , Description and yes   even numbers  
    // 2.  So the backpack capacity is sum / 2
    bool canPartition(vector<int>& nums) {
    
        int sum = 0;
        for (int i = 0; i < nums.size(); i++)
            sum += nums[i];
        
        if (sum & 1) return false; //  Odd number , immediate withdrawal 
        sum /= 2;
        int dp[sum + 1];
        for (int i = 0; i < sum + 1; i++)
            dp[i] = 0;
        
        for (int i = 0; i < nums.size(); i++) {
    
            for (int j = sum; j >= nums[i]; j--)
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
        }

        if (dp[sum] == sum) return true;
        return false;
    }
};