题目描述
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
输入:nums = [1,5,11,5]
输出:true
解释:数组可以分割成 [1, 5, 5] 和 [11] 。
首先nums
元素和sum
必须是偶数,否则false
转换成01背包问题,放入nums
中的一些数字,能够得到和为sum/2
所以对每个元素,可以放可以不放dp[i][j]
表示截止到第i个元素,能够得到和为j
的情况。dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i]]
前者表示在i
号元素之前就可以得到,后者在j>=nums[i]
时,表示放入第i
号元素,在此之前需要能够凑到和为j-nums[i]
最后输出dp[nums.size()-1][sum/2]
class Solution { public: bool canPartition(vector<int>& nums) { int sum=0; for(auto i:nums) sum+=i; if(sum&1) return false; vector<vector<bool>> dp(nums.size(),vector<bool>(sum/2+1,false)); //行号是数组元素,从dp[0]-dp[nums.size()] //列号是可以求得的和,从dp[][0]-dp[][sum/2] int target=sum/2; if(nums[0]==target) return true; if(nums[0]<target) dp[0][nums[0]]=true; for(int i=1;i<nums.size();i++){ for(int j=0;j<target+1;j++){ dp[i][j]=dp[i-1][j]; if(nums[i]==target) return true; if(nums[i]<=j) dp[i][j]=dp[i-1][j]||dp[i-1][j-nums[i]]; //一种是不选nums[i],但是前面已经能够得到和为j //另一种是选nums[i],且前面能得到和为j-nums[i] } } return dp[nums.size()-1][target]; } };