Problem 27: Equal Sum Partition

Problem Statement: Given an array of n positive integers, determine if it is possible to partition the array into two subsets such that the sum of the elements in both subsets is equal.

Input

The first line contains the integer n. The next line contains n space-separated integers.

Output

Print "YES" if such a partition exists, otherwise print "NO".

Examples


Input:
4
1 5 11 5

Output:
YES

Solution Explanation

Method 1: Use dynamic programming to determine if there exists a subset that sums up to half of the total sum. Method 2: Use recursion with memoization to check all possible subset sums, but DP is generally more efficient.

Solution in C++


#include 
#include 
#include 
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    vector a(n);
    int sum = 0;
    for (int i=0; i> a[i];
        sum += a[i];
    }
    if(sum % 2 != 0){
        cout << "NO
";
        return 0;
    }
    int target = sum/2;
    bitset<10001> dp;
    dp[0] = 1;
    for (int x : a) {
        dp |= dp << x;
    }
    cout << (dp[target] ? "YES" : "NO") << "
";
    return 0;
}