416. Partition Equal Subset Sum

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

NOTE:
1. Each of the array element will not exceed 100.
2. The array size will not exceed 200.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int canPartition(int *nums, int numsSize);

int main()
{
    int nums[] = {1,5,11,5};
    int n = 4;
    int can = 0;

    can = canPartition(nums,n);
    printf("result is: %d\n",can);

    return 0;
}

int canPartition(int *nums, int numsSize)
{
    int i = 0, j = 0;
    int total = 0;
    int half = 0;
    int max = 0;
    int *sum; // sum[i]=1表示和等于i

    for(i = 0; i < numsSize; i++)
    {
        total += nums[i];
        max = max > nums[i] ? max : nums[i];
    }

    if(total%2) return 0; // 和为奇数，不能划分为等和子集
    if(max > total/2) return 0; // 最大元素大于和的一半，不能划分为等和子集

    half = total/2;
    sum = (int *)malloc((half+1)*sizeof(int));
    memset(sum,0,(half+1)*sizeof(int));

    sum[0] = 1; // 和等于0一定成立，空集就行
    for(i = 0; i < numsSize; i++)
    {
        for(j = half; j >= nums[i]; j--)
        {
            if(sum[j-nums[i]])
            {
                sum[j] = 1;
                if(j == half)
                {
                    return 1;
                }
            }
        }
    }

    return 0;
}