[Leetcode] 416. Partition Equal Subset Sum (C++)
문제
416. Partition Equal Subset Sum
코드
// dfs - Time Limit Exceeded
class Solution {
public:
bool canPartition(vector<int>& nums) {
int target = accumulate(nums.begin(), nums.end(), 0);
if (target%2 == 1) return false;
return recur(nums, 0, 0, target/2);
}
bool recur(vector<int>& v, int idx, int cur, int target){
if (cur == target) return true;
for (int i = idx; i < v.size(); i++){
if (cur+v[i] <= target and recur(v, i+1, cur+v[i], target)) return true;
}
return false;
}
};
// Accepted
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = accumulate(nums.begin(), nums.end(), 0), target = sum >> 1;
if (sum & 1) return false;
vector<int> dp(target + 1, 0);
dp[0] = 1;
for(auto num : nums)
for(int i = target; i >= num; i--)
dp[i] = dp[i] || dp[i - num];
return dp[target];
}
};
접근
먼저 두 subset의 합이 동일해야 하기 때문에 총합이 짝수여야 한다는 점을 떠올렸다. 또한 해당 원소를 가지는 경우와 아닌 경우 모두를 살펴보면 답이 나오겠거니 생각했고 실제로 답은 구할 수 있었다. 하지만 제한사항에서 보면 알 수 있듯이 입력 배열의 크기가 200이하이기 때문에 이렇게 배열의 길이가 200 이라면 시간 복잡도가 O(N^200)이 되지 않나 생각했고 실제로 시간초과가 되었다.
그래서 dp로 접근해야 하나 싶었다. 언뜻 생각했을 때 지수 시간복잡도가 나오진 않기 때문에 시도해보았다. 궁극적으로 target에 도달할 수 있는지가 중요한 부분이기 때문에 이를 확인할 수 있는 배열을 하나 만들었다. target부터 현재 값까지를 살피면서 현재 값을 빼서 뺀 것과 빼지 않은 것, 즉 현재 위치 혹은 이 원소로 도달할 수 있는 위치가 1로 체크되어있는지를 확인했다. 1로 세팅이 되었다는 것은 그 값이 도달할 수 있다는 것을 의미한다. 또한 0은 항상 도달가능하기 때문에 1로 초기화 해두었다.
Author And Source
이 문제에 관하여([Leetcode] 416. Partition Equal Subset Sum (C++)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@keybomb/Leetcode-416.-Partition-Equal-Subset-Sum-C저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)