[LeetCode] 416. Partition Equal Subset Sum (C++)

 

 

난이도: Medium

Problem Description

---

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.

 

Problem Example

---

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 <= 200
• 1 <= nums[i] <= 100

 

✏️ Solution

---

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum_num = accumulate(nums.begin(), nums.end(), 0);

        if (sum_num % 2 != 0){
            return false;
        }

        int div_sum_num = sum_num / 2;
        vector<bool> dp(div_sum_num+1, false);
        dp[0] = true;

        for (int num:nums){
            for(int i = div_sum_num; i >= num; --i){
                dp[i] = dp[i] || dp[i-num];
            }
        }
        
        return dp[div_sum_num];
    }
};

먼저 nums의 모든 수를 더하고, 이 수가 홀수라면 false를 반환했다.

 

홀수이면 2개로 어떻게 나눠도 같은 합을 갖는 subset들을 구할 수 없기 때문이다.

 

짝수일 경우, 전체 합의 절반인 div_sum_num 값을 목표로 하여 해당 값을 만들 수 있는 부분집합이 존재하는지를 판별한다.

이를 위해 dp[i]를 "합이 i인 부분집합을 만들 수 있는가?"를 나타내는 boolean 벡터 배열로 정의하고, 초기값으로는 dp[0] = true로 설정하였다. 이는 아무 것도 선택하지 않았을 때 합이 0이 되는 경우가 항상 존재하기 때문이다.

이후 nums의 각 숫자 num에 대해, 현재 숫자를 사용했을 때 만들 수 있는 합들을 역순으로 갱신한다.

갱신은 dp[i] = dp[i] || dp[i - num] 방식으로 이루어지며, 이는 num을 사용하지 않더라도 i를 만들 수 있는 경우를 유지하고, num을 사용해서 i를 만들 수 있다면 true로 변경한다는 의미다.

마지막에는 dp[div_sum_num] 값을 반환하여 정답을 맞출 수 있었다.

 

 

⚙️ Runtime & Memory

---

 

 

---

문제: 416. Partition Equal Subset Sum