subset-sum-problem.md

Partition Equal Subset Sum

Given an array arr[] of size N, check if it can be partitioned into two parts such that the sum of elements in both parts is the same.

Sample Input

4
1 5 11 5

Sample Output

YES

Solution

class Solution {
public:
    int equalPartition(int N, int arr[])
    {
        sort(arr, arr+N);

	    int sum = accumulate(arr, arr + N, 0);

	    if(sum & 1) return 0;

	    int half = sum/2;

	    vector< vector<int> > dp(N + 1, vector<int>(half + 1, 0));

	    for(int i = 0; i < N; ++i) {
	        for(int j = 1; j <= half; ++j) {
	            if(j < arr[i]) {
	                dp[i+1][j] = dp[i][j];
	                continue;
	            }
	            dp[i+1][j] = max({arr[i], dp[i][j - arr[i]] + arr[i], dp[i][j]});
	        }
	    }

        return half == dp.back().back();
    }
};

Accepted