416. 分割等和子集

题目

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

思路

因为这道题要判断数组能否分割成两个和相等的子集，这样的话所有书的总和一定是可以平分成两份的，所以一定是偶数。首先判断数组长度，长度小于2肯定无法平分为两份，元素总和为奇数也无法平分，直接返回false。如果总和为偶数，目标和为总和的一半，然后就判断最大元素，最大元素超过目标和，也无法分割。求解需要定义dp[j]表示能否凑出和为j的子集，初始时dp[0]为1（空集和为0）。然后遍历每个元素，逆序更新dp数组：对每个元素num，从目标和倒序到num，如果dp[j-num]为true（即能凑出j-num），则dp[j]也为1（选num后凑出j），逆序遍历是为避免同一元素重复使用。最后查看dp[t]是否为true，如果为true则能分割，否则不能。

代码

class Solution {
public:bool canPartition(vector<int>& nums) {int n=nums.size(),t;if(n<2){return false;}int sum=0,m=0;for(auto& num:nums){sum+=num;//求所有数的和m=max(m,num);//找到里面最大的一个数}if(sum&1){return false;//所有数的和是奇数，无法使得两个子集的元素和相等}t=sum/2;//元素和的值if(m>t)//最大元素大于元素和就无法满足条件{return false;}vector<int> dp(t+1,0);//表示是否存在一种选法，让选出的数总和是jdp[0]=1;//和为0的子集总是存在for(int i=0;i<n;i++){int num=nums[i];for(int j=t;j>=num;j--){//对于每个j，如果j-num可达到要求（dp[j - num]为1），则j也可达dp[j]|=dp[j-num];//不选当前元素或选当前元素两种情况}}return dp[t];}
};