MinAbsSum

#include <algorithm>
#include <cmath>
#include <numeric>

int solution(vector<int> &A) {
    
    int n = A.size();
    if (n == 0) {
        return 0;
    }
    
    int M = 0;
    int S = 0;
    for (int i = 0; i < n; i++) {
        A[i] = abs(A[i]);
        M = max(M, A[i]);
        S += A[i];
    }

    vector<int> count(M + 1, 0);
    for (int i = 0; i < n; i++) {
        count[A[i]]++;
    }

    vector<int> dp(S + 1, -1);
    dp[0] = 0;

    for (int a = 1; a < M + 1; a++) {
        if (count[a] > 0) {
            for (int j = 0; j < S / 2 + 1; ++j) {
                if (dp[j] >= 0) {
                    dp[j] = count[a];
                }
                else if (j >= a && dp[j - a] > 0) {
                    dp[j] = dp[j - a] - 1;
                }
            }   
        }
    }
    
    int result = S;
    for (int i = 0; i < S / 2 + 1; ++i) {
        if (dp[i] >= 0) {
            result = min(result, S - 2 * i);
        }
    }
    return result;
}