[leetcode 416] Partition Equal Subset Sum

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:

1. Each of the array element will not exceed 100.
2. The array size will not exceed 200.

 

Example 1:

Input: [1, 5, 11, 5] Output: true Explanation: The array can be partitioned as [1, 5, 5] and [11].

 

Example 2:

Input: [1, 2, 3, 5] Output: false Explanation: The array cannot be partitioned into equal sum subsets.

 

기본적인 접근:

배열 전체의 수를 더한다. 만약 total sum이 홀수면 두 집합으로 나눌수 없으므로 return false

목표는 subtotal에 해당하는 두 개의 집합을 만드는 것

 

접근

1. 브루트포스

TLE난다 ㅎㅎ

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        
        int total=0;
        for(int num: nums){

            total += num;
        }
        
        if(total %2 != 0) return false;
        
        int subtotal = total/2;
        int n = nums.size();
        return dfs(nums, n-1, subtotal);
    }
    
    
    bool dfs(vector<int> &nums, int sze, int sub){
        if(sub == 0){
            return true;
        }else if(sze == 0 || sub<0){
            return false;
        }
        
        bool result = dfs(nums, sze-1, sub-nums[sze-1]) || dfs(nums, sze-1, sub);
        return result;
    }
};

 

2. bottom up -> 일반적인 dp

 

dp[i][j] = num[0]부터 num[i]까지 사용해서 합 j를 만들어낼 수 있는지 bool이다.

현재 배열 값을 cur라 하고 목표값이 j라면

기본적으로 dp[i][j] = dp[i-1][j]이다. 왜냐면 i-1개로 j를 만들 수 있으면 당연히 i개로도 j를 만들수 있기 때문

하지만 j< cur인 경우 i번째 nums[i]를 추가한다고 해서 더 작은 j가 만들어질 수 없기 때문에 dp[i-1][j]만 따진다.

반면에  j>cur인 경우, dp[i][j]는 dp[i-1][j]가 true거나 dp[i-1][j-cur]이 true면 true가 된다. j가 cur보다 크기 때문에 i-1번째에 cur을 뺀수를 sum으로 만들 수 있다면 nums[i]인 cur을 추가하면 당연히 dp[i][j]가 트루가 된다.

 

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        
        int total=0;
        for(int num: nums){

            total += num;
        }
        
        if(total %2 != 0) return false;
        
        int subtotal = total/2;
        int n = nums.size();
        
        int dp[n+1][subtotal+1];
        
        memset(dp, 0, sizeof(dp));
        
        dp[0][0]=1;
        
        for(int i=1; i<=n; i++){
            int cur = nums[i-1];
            for(int j=0; j<= subtotal; j++){
                if(j<cur){
                    dp[i][j] = dp[i-1][j];
                }else {
                    dp[i][j] = dp[i-1][j] || dp[i-1][j-cur];
                }
            }
        }
        
        return dp[n][subtotal];
    }

};