题解 | #分割等和子集#

#include <vector>
class Solution {
public:
    //dp[j]：容量为j的背包中能装下的物品的最大价值为dp[j]，在本题中j的最大值是数组和的一半，当dp[j]=j，也就是正好有一种情况，能满足让某些数字构成数组和的一半时，剩下的数字自然也能构成另一半，因此就能满足题意了。
    //递推公式：由于使用的是滚动背包，以将空间复杂度从nxv降低到v，所以每一次遍历时都是用j的值从后往前覆盖掉j-1的值。
    //在二维背包里，dp[i][j]=max(dp[i-1][j] 即不放物品i, dp[i][j-weight(i)]+value(i) ),而在滚动背包中由于在更新j时原本的数组里存留着i-1的值，所以比较dp[j]的值就相当于比较dp[i-1][j]的值。
    //因此递推公式为dp[j]=max(dp[j] , dp[j-weight(i)]+value(i) )。
    //也因为这个原因，遍历顺序为先遍历物品，再遍历容量，容量需要倒着遍历，避免左侧的值被重复使用。
    //初始化需要初始化为一个比装任何物品都绝对要更小的值。元素价值都为正值时初始化为0，若有负值，则需要初始化为INT_MIN。
    bool partition(vector<int>& nums) {
        int sum=0;
        for(auto num:nums)
        {
            sum+=num;
        }
        if(sum % 2==1)return false;
        int maxj=sum/2;
        vector<int>dp(maxj+1,0);//全部初始化为0，因为元素都为正整数。
        for(int i=0;i<nums.size();i++)
        {
            for(int j=maxj;j>0;j--)//dp[0]无需遍历，啥也放不进去。因为元素为正整数，大于0，所以不存在weight为0的物品。
            {
                if(j<nums[i])break;
                dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        if(dp[maxj]==maxj)return true;
        return false;
    }
};