[Leetcode] *416. Partition Equal Subset Sum

문제 

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.
 
Example 1:
Input: nums = [1,5,11,5] Output: true Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:
Input: nums = [1,2,3,5] Output: false Explanation: The array cannot be partitioned into equal sum subsets.
 
Constraints:
1 <= nums.length <= 2001 <= nums[i] <= 100

 

풀이

 

이 문제는 dynamic programming을 쓰면 된다.

dp는 큰 문제를 작은 문제로 나눠서 푸는 것인 만큼, total_sum/2 가 만들어질수 있는지 없는지 하나씩 구해가면 된다.

 

이 문제에서 dp는 nums에서 만들 수 있는 모든 sum를 true로 표시한다.

dp[0]을 true로 intialize 해서 nums[i] 만큼 떨어진 모든 수를 true로 바꿔 진행해, dp[total_sum/2] = true가 될 때까지 진행한다.

 

코드

int cmp(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

bool canPartition(int* nums, int numsSize) {
    int sum = 0;
    for(int i=0; i<numsSize; i++) {
        sum+=nums[i];
    }
    int target = sum/2;
    if(sum%2) return false;
    // sort first
    qsort(nums, numsSize, sizeof(int), cmp);

    bool dp[target+1]; // if sum is available at index
    memset(dp, false, sizeof(dp));
    dp[0] = true;

    for(int i=0; i<numsSize; i++) {
        for(int j = target; j>=nums[i]; j--) {
            dp[j] |= dp[j - nums[i]];
        }
        if(dp[target]) break;
    }

    return dp[target];
}