Day42| Leetcode 416. 分割等和子集

01一维和二维背包

Leetcode 416. 分割等和子集

题目链接 416 分割等和子集

本题目第一个反应是用回溯法，但是会超时，用dp滚动数组是最优的，但是这里要注意，容量和价值是相同的，也就是说只要让target == dp[target]即可，如果target为奇数，也没法满足要求。下面上代码：

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        vector<int> dp(10005,0);//初始化为0；
        for(int i=0;i<nums.size();i++){
            sum+=nums[i];
        }
        int target = sum/2;
        if(sum%2 == 1){//奇数不可能
            return false;
        }
        //01背包，特殊的地方是重量和价值相等
        for(int i=0;i<nums.size();i++){
            for(int j=target;j>=nums[i];j--){
                dp[j] = max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        if(dp[target] == target){//重量和价值相等
            return true;
        }
        return false;
    }
};