题目描述
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
示例
输入:nums = [1,5,11,5] 输出:true 解释:数组可以分割成 [1, 5, 5] 和 [11] 。
解题思路
这一个背包问题的应用。背包问题相关可以看https://github.com/youngyangyang04/leetcode-master/blob/master/problems/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-1.md
对于本题,如果只有一个数,要返回false;如果所有数的和为奇数,也要返回false;
接着我们可以根据背包问题,背包的容量target=sum/2;且物品的价值和重量都为该数本身的值,那我们只需要求得第n个数在容积为target的解是否等于target。如果不等的话,那么就return false;
代码
class Solution { public: bool canPartition(vector& nums) { int n=nums.size(); if(n==1) return false; int i,j; int sum=0; for(i=0;i target) { return false; } } vector > dp(n,vector (target+1,0)); for(j=nums[0];j<=target;j++) { dp[0][j]=nums[0]; } for(i=1;i j) { dp[i][j]=dp[i-1][j]; } else{ dp[i][j]=max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i]); } } } if(dp[n-1][target]==target) return true; return false; } };
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)