https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=503

562 - Dividing coins.cpp

#include <bits/stdc++.h>

#define ll long long
#define sz(v) ((int) ((v).size()))
#define clr(v, d) memset(v, d, sizeof(v))
#define lp(i, n) for(int i = 0; i < (int)(n); ++i)
#define rep(i, v) for(int i = 0; i < sz(v); ++i)

using namespace std;

const int MAX = 105;
const int OO = 1e9;

int n, total;
int a[MAX];
int cache[MAX][50005];

int minDiff(int i, int sum) {
    if(i == n)
        return abs(total - 2*sum);
    int &ret = cache[i][sum];
    if(ret != -1)
        return ret;
    int ch1 = minDiff(i+1, sum+a[i]);
    int ch2 = minDiff(i+1, sum);

    return ret = min(ch1, ch2);

}


int main() {
    int t;
    cin>>t;
    while(t--) {
        total = 0;
        clr(cache, -1);
        cin>>n;
        lp(i, n) {
            cin>>a[i];
            total+=a[i];

        }
        //cout << "total :  " << total << endl;
        cout << minDiff(0, 0) << endl;
    }

    return 0;
}