LeetCode416：分割等和子集

题目链接：416. 分割等和子集 - 力扣（LeetCode）

代码如下：

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int m = nums.size();
        vector<int> dp(10010, 0);
        int sum = 0;
        for(int i = 0; i < m; i++)
        {
            sum += nums[i];
        }
        if(sum % 2 == 1)    return false;
        int target = sum / 2;
        for(int i = 0; i < m; 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;
    }
};

代码讲解：这个题目首先我们要明白一件事情，就是要把这个分成一个相等的子集，那么其实我们就可以看似为一个01背包问题，怎么去转化为这个01背包，就是我们先把所有的子集加起来除以2，就是背包大小，看看里面的子集能不能刚刚好填满这个背包，要是能的话，返回true，否则返回false，这个里面要注意的是，if（sum % 2 == 1）return false;这个原因是因为要是奇数的话，有小数点，你放进去的东西不能够是半个吧，因为题目都给你的全是整形数据。

原文地址：https://blog.csdn.net/Ricky_youngone/article/details/142463727

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！