Problem 77: Balanced Partition Problem

Problem Statement: Given an array of integers, partition them into two subsets such that the absolute difference of their sums is minimized.

Input

The first line contains an integer n. The second line contains n space-separated integers.

Output

Print the minimum absolute difference between the sums of the two partitions.

Examples


Input:
4
1 6 11 5

Output:
1

Solution Explanation

Use dynamic programming to detect all possible subset sums. The answer is the minimum of |total_sum - 2*subset_sum| where subset_sum is no larger than total_sum/2.

Solution in C++


#include 
#include 
#include 
using namespace std;

int main(){
    int n; 
    cin >> n;
    vector a(n);
    int total = 0;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        total += a[i];
    }
    vector dp(total + 1, false);
    dp[0] = true;
    for(int x : a){
        for(int s = total; s >= x; s--){
            dp[s] = dp[s] || dp[s - x];
        }
    }
    int ans = total;
    for(int s = 0; s <= total / 2; s++){
        if(dp[s]) ans = min(ans, total - 2 * s);
    }
    cout << ans << "\n";
    return 0;
}