给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。
这题是很经典的动态规划算法，说实在的，我最近也是慢慢的觉得这个算法也不错，也得到一些启发
下面是标准动态规划算法，但其实一般般
bool canPartition(int* nums, int numsSize) {
if (numsSize < 2) {
return false;
}
int sum = 0, maxNum = 0;
for (int i = 0; i < numsSize; ++i) {
sum += nums[i];
maxNum = fmax(maxNum, nums[i]);
}
if (sum & 1) {
return false;
}
int target = sum / 2;
if (maxNum > target) {
return false;
}
int dp[numsSize][target + 1];
memset(dp, 0, sizeof(dp));
for (int i = 0; i < numsSize; i++) {
dp[i][0] = true;
}
dp[0][nums[0]] = true;
for (int i = 1; i < numsSize; i++) {
int num = nums[i];
for (int j = 1; j <= target; j++) {
if (j >= num) {
dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[numsSize - 1][target];
}
我下面改进了这个算法，代码如下：
bool canPartition(int* nums, int numsSize){
int i=0;
int target;
if(numsSize<2){
return false;
}
int sum=0;
for(i=0;i
sum=sum+nums[i];
}
if(sum%2==1)return false;
else target=sum/2;
int dp[target+1];
for(i=0;i
dp[i]=0;
}
dp[0]=1;
int j=0;
int len =1;
int tnum[target+1];
tnum[0]=0;
printf(" target %d ",target);
for(i=0;i
int num=nums[i];
int t=len;
for(j=0;j
if(num+tnum[j]==target){
return true;
}
if(num+tnum[j]<=target){
if(dp[num+tnum[j]]==0){
dp[num+tnum[j]]=1;
tnum[t++]=num+tnum[j];
}
}
}
len=t;
}
return false;
}
