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.

• Time : O(n * sum)
• Space : O(sum)

c++

class Solution {
public:
    int equalPartition(int N, int arr[]) {
        int sum = accumulate(arr, arr + N, 0);
        if(sum & 1) return false;
        vector<bool> dp(sum / 2 + 1);
        dp[0] = true;

        for(int i = 0; i < N and !dp[sum / 2]; i++) {
            for(int j = sum / 2; j >= arr[i] and !dp[sum / 2]; j--) {
                if(dp[j - arr[i]]) dp[j] = true;
            }
        }

        return dp[sum / 2];
    }
};