分割等和子集-c语言动态规划算法和改进算法同时提升时间复杂度和空间复杂度

分割等和子集

给你一个 只包含正整数 的 非空 数组 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<numsSize;i++){
        sum=sum+nums[i];

    }
    if(sum%2==1)return false;
    else  target=sum/2;
   
    int dp[target+1];
     for(i=0;i<target+1;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<numsSize;i++){
        int num=nums[i];
        int t=len;
        for(j=0;j<len;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;

}