UAIC Competitive Programming

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 in C++


#include <iostream>
#include <vector>
#include <bitset>
using namespace std;

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