[C] LeetCode 416. Partition Equal Subset Sum

 

문제

번역

정수 배열 nums가 주어졌을 때, 배열을 2개의 부분 배열로 나누었을 때 두 배열의 합이 같으면 true를 반환해라.

그렇지 않으면 false를 반환해라.

접근 방법 및 소스 코드

일단, 배열의 합이 홀수이면 그 어떤 경우의 수로 나누어도 두 부분배열의 합이 같아질 수 없다.

 

이 문제를 풀기 위해서는 부분배열의 합 = 전체 배열의 합 / 2 인지를 확인해야 한다.

즉 nums에서 몇 개의 수를 골라서 전체 합 / 2를 만들 수 있는지 확인하면 된다.

 

bool dp[10001];
bool canPartition(int* nums, int numsSize) {
    memset(dp,  0, sizeof(dp));
    int s=0;
    for(int i=0;i<numsSize;i++) s+=nums[i];
    if(s%2) return false;
    dp[0]=true;
    for(int i=0; i<numsSize; i++) {
        int t = nums[i];
        for(int j = s/2; j >= t; j--) {
            dp[j] = dp[j] || dp[j - t];
        }
    }
    return dp[s/2];
}