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;
}