UVa 562 - Dividing coins

// UVa 562 - Dividing coins

#include <iostream>
#include <string.h>
#include <vector>
using namespace std;

#define MaxC 100
#define MaxS 50000

int main() {
	int cases;
	for (cin >> cases; cases; cases--) {
		int n;
		int c[MaxC];
		cin >> n;
		int total_sum = 0;
		for (int i = 0; i < n; i++) {
			cin >> c[i];
			total_sum += c[i];
		}
		bool yet[MaxS];
		memset(yet, true, sizeof(yet));
		vector<int> g;
		yet[0] = false;
		g.push_back(0);
		for (int i = 0; i < n; i++) {
			int m = g.size();
			for (int j = 0; j < m; j++) {
				if (yet[g[j] + c[i]]) {
					g.push_back(g[j] + c[i]);
					yet[g[j] + c[i]] = false;
				}
			}
		}
		int left = total_sum / 2;
		int right = total_sum - left;
		while (yet[left] && yet[right]) {
			left--;
			right++;
		}
		cout << right - left << endl;
	}
	return 0;
}