Leetcode 416. Partition Equal Subset Sum

[集合能不能分成2个相等的子集]

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

Note:
Each of the array element will not exceed 100.
The array size will not exceed 200.
?
Example 1:
Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:
Input: [1, 2, 3, 5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

• 数字是物品重量，和的一半是背包，dp记录true or false

• 初始化时，dp全为flase

• 状态转移为 左边和上面的与 dp[v] = dp[v] || dp[v-w[i]]

• 注意从后面开始遍历，不然下图的1那一行会变成都是True

• 同样注意 dp[0]初始化为true，这样才能使 重1的物品面对1体积背包时候，d[1] = d[1](初始化为false） || d[1-1] = true

如图，令集合为1 5 11 5 sum一半是1，背包从0到12

这该死的长度限制 cnblog改一下

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        int sum=0;
        for (int num : nums) sum += num;
        if(sum % 2) return false;
        sum = sum/2;
        vector<bool> dp(sum+1, false);
        dp[0] = true;
        for(int i=0;i<n;i++){
            for(int j=sum;j>=nums[i];j--){
                dp[j] = dp[j] || dp[j-nums[i]];
            }
        }
        return dp[sum];
    }
};

Leetcode 416. Partition Equal Subset Sum

原文：https://www.cnblogs.com/islch/p/12599422.html