[数据结构与算法]Leetcode.0416 | 分割等和子集

题目

给你一个?只包含正整数?的?非空?数组?nums?。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

解决方法

本题的解法类似于Leetcode.0494 | 目标和_畅春园-CSDN博客，属于0-1背包问题。该问题可以转化为：给定一个数组以及容量为 (数组各个元素之和)/2 的背包，求解是否能够恰好使得背包能够装满。

设dp[j] 表示要装满容量为j的背包，能否成功。外层对nums数组从前到后进行遍历，内层对j从?(数组各个元素之和)/2 到nums[i]进行遍历。物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历。

对计算公式为： dp[j] = dp[j] | dp[j-nums[i]] ，对于当前的第i个物品，有拿和不拿两种情况，dp[i]表示不拿的情况，dp[m-nums[i]]表示拿的情况，如果二者之间有一种能够使得背包装满，那么此时背包就能装满。

代码实现

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