416-分割等和子集

LeetCode 416. Partition Equal Subset Sum

LeetCode-416

Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Example 1:

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

method: 01背包

背包重量为数组和的一半，看最后是否能刚好放满

每个元素都是一件物品，重量和价值相等

bool canPartition(vector<int>& nums) {
    int sum = 0;
    for (int i = 0; i < nums.size(); i++)
        sum += nums[i];     // 累加
    if (sum % 2) return false;  // 和为奇数直接返回
    sum /= 2;   // 背包重量
    vector<int> dp(sum + 1, 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]);
        }
    }
    return dp[sum] == sum;  // 是否放满
}