---

dp专题7 分割等和子集

原创 于 2024-01-02 15:55:32 发布 · 粉丝可见 · 461 阅读 · 10 · 11 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/135342603

本题链接： 力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题目：

思路：

由题意，题目意思是给出数组nums  找出两个子集它们的元素和相等。

这里两个自己的元素和相等，说明需要 数组 nums 总和可以平分，即 sum % 2 == 0

又因为子集不要求我们所取的元素是连续的，这里只有取或不取，所以我们试着取联想以下 01 背包

其中 容量是 我们的 sum / 2 ，只要我们取的 nums 元素之和 刚好满足 sum / 2 即可，所以我们的 元素中的  价值 和 体积 都是 nums[] 元素值

代码详解如下：

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        vector<int>dp(200*100+10,0);   // 定义 dp 数组
        int sum = 0;    // 计算 （背包容量） 元素和
        for(int &i:nums) sum += i;
        if(sum % 2) return false;   // 如果元素和无法平分，返回 false
        else sum /= 2;
        
        // 开始遍历元素
        for(int &i:nums)
        {
            // 遍历（背包容量） 到达的平分元素和
            for(int j = sum ;j >= i;--j)
            {
                dp[j] = max(dp[j],dp[j - i] + i);
            }
        }
        
        return dp[sum] == sum;
    }
};

最后提交：