416. Partition Equal Subset Sum(数组中有无相等子数组和)

た入场券 2023-02-12 10:26 13阅读 0赞

题目：  
给定一个仅包含正整数的非空数组，请确定该数组是否可以划分为两个子集，以使两个子集中的元素之和相等。  
注意：

每个数组元素将不超过100。  
阵列大小不会超过200

思路：  
　　 将数组分为两个子数组，一组得和为P集合，另一组为M集合。求sum P= sum M 是否成立。  
　　 化简后可以利用sum(nums)来计算出其中一个P。再利用dp动态规划来从P开始记录（dp\[0\]==1）方便设置为1.当P-其他的和 ==0了。  
注意其中得ｄｐ数组可能会溢出问题。  
ｃｏｄｅ：

class Solution { 
    public:
        bool canPartition(vector<int>& nums) { 
            int sum=accumulate(nums.begin(),nums.end(),0);
            if(sum%2)
                return false;
            
            int target=sum/2;
            vector<double > dp(target+1);			//之前是int
            dp[0]=1;
            for(int n:nums)
            { 
                if(n>target)
                    return false;   //说明不可能有哪个子数组。最大只能为target
                for(int i=target; i>=n; i--)
                { dp[i]+=dp[i-n];
                 if(dp[target])
                     return true;
                }
            }
            return dp[target];
            
        }
    };

为什么溢出呢?  
在leetcode中会溢出错误.改成double(8字节得)就好了.  
但是在vscode中运行是没有问题得.