[Dynamic Programming][Medium] 416. Partition Equal Subset Sum

 

https://leetcode.com/problems/partition-equal-subset-sum/description

 

Q. 1부터 200까지의 수 배열 nums가 있을 때, 이 배열의 각기 합을 같게 만들어 2개로 분할하는 subset이 존재하는지 여부를 반환하라. 

 

Solution. 

  예제에서 보는 바와 같이, 연속되는지 여부에 관계없이 2개로 그 합이 같도록 분할되면 될 것이다. 

  우선 전체 합이 필요하다. 그 후 반으로 나눈 값을 배열을 순차적으로 지나며

  그 값으로 빼거나, 말거나 

  계산 값을 끝까지 지속하며, 이 값이 0이 되면, 이미 반이 된 값이므로, 나눠진다는 것이고, 

  그렇지 않다면 나눠지지 않는다는 것이다. 

  이때, 양수입력만 있으므로, 도중에 - 값이 되면 바로 실패로 간주 할 수 있을 것이다. 

  같은 원리로, 도중에 0 이 된다면, 뒤는 포함하지 않으면 되므로, 바로 성공으로 간주 할 수 있을 것이다. 

 

  

bool canPart(vector<vector<int>>& vCache, vector<int>& nums, int idx, int target)
{
    if(target == 0) return true;
    if(target < 0)  return false;
    if(idx >= nums.size())
        return false;

    if(vCache[idx][target-1] >= 0)
        return vCache[idx][target-1];

    if(canPart(vCache, nums, idx+1, target-nums[idx]))
        return vCache[idx][target-1] = 1;

    return vCache[idx][target-1] = canPart(vCache, nums, idx+1, target) ? 1 : 0;
}

bool canPartition(vector<int>& nums) 
{
    int sum = 0;
    for(int q = 0; q < nums.size(); ++q)
        sum += nums[q];
    if(sum%2 == 1)  return false;

    sum /= 2;
    vector<vector<int>> vCache(nums.size(), vector<int>(sum, -1));
    return canPart(vCache, nums, 0, sum);
}

 

적당한 결과를 얻었다. 

 

 

Note 1 ) 이 문제는 동전 문제와 매우 비슷하다. 

Note 2) 캐싱에서 늘 map 보다 vector가 빠르다. 이 예제처럼 극단적으로 buffer를 낭비해야 하는 상황에서도, vector를 쓰는 캐싱이 아니면 timelimitation에 걸려 실패했다. 

 또한 낭비되는 buffer가 많아 보여도, 최종 메모리는 map을 사용 했을때 보다 1/5 가량 적게 사용 됐다.