leetcode416. 分割等和子集

416. 分割等和子集 - 力扣（LeetCode） (leetcode-cn.com)

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

由题目可以知道要将数组nums分成两个子集，且元素和相等，我们可以提炼出一个信息那就是nums数组的和一定不能为奇数，如果是奇数的话那两个子集中肯定会出现小数，那就不符合只包含正整数这一条件了。然后我们再将大问题转化为小问题，因为他说判断是否可以将这个数组分割成两个数组且两个数组的和相等，那就可以说明其中一个数组子集的和是原来数组的和的一半。

就把问题转化为背包问题

对比背包问题我们定义了一个二维数组dp[i][j]表示的是前i个物品背包容量最大为j所能装下的最大价值，而这题dp[j]表示 背包总容量是j，最大可以凑成j的子集总和为dp[j]。

所有这题的递推式和背包问题的递推式一样

dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);

操作方法都和01背包一样

最后如何判断这个数组是否能分为两个子数组

就看dp[mid]是否等于mid。

原因就是原数组的和为sum如果存在一个拆成mid则另一个也存在

x=sum-mid;这x等于mid

完整代码

int max(int a,int b)
{
    return a>b?a:b;
}
bool canPartition(int* nums, int numsSize){
 int dp[10000]={0},sum=0;  //定义dp数组

for(int i=0;i=nums[i];j--)  //01背包模板
    {
        dp[j]=max(dp[j],dp[j-nums[i]]+nums[i]);
    }
}
if(dp[mid]==mid)return true;  //判断dp[mid]是否为mid
return false;
}