UVa 10482 - The Candyman Can

// UVa 10482 - The Candyman Can
#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;

int main() {
	int tt;
	cin >> tt;
	for (int t = 1; t <= tt; t++) {
		int n;
		cin >> n;
		int w[33];
		int sum = 0;
		for (int i = 0; i < n; i++) {
			cin >> w[i];
			sum += w[i];
		}

		bool yet[641][641];
		memset(yet, true, sizeof(yet));
		int gen[409602][2];
		int sol = 640;
		long int m = 1;
		gen[0][0] = 0;
		gen[0][1] = 0;
		for (int i = 0; i < n; i++) {
			for (long int j = m - 1; j >= 0; j--) {
				int a = gen[j][0];
				int b = gen[j][1];
				if (yet[a + w[i]][b]) {
					yet[a + w[i]][b] = false;
					gen[m][0] = a + w[i];
					gen[m][1] = b;
					int mn = min(min(gen[m][0], gen[m][1]), sum - gen[m][0] - gen[m][1]);
					int mx = max(max(gen[m][0], gen[m][1]), sum - gen[m][0] - gen[m][1]);
					if (mx - mn < sol)
						sol = mx - mn;
					m++;
				}
				if (yet[a][b + w[i]]) {
					yet[a][b + w[i]] = false;
					gen[m][0] = a;
					gen[m][1] = b + w[i];
					int mn = min(min(gen[m][0], gen[m][1]), sum - gen[m][0] - gen[m][1]);
					int mx = max(max(gen[m][0], gen[m][1]), sum - gen[m][0] - gen[m][1]);
					if (mx - mn < sol)
						sol = mx - mn;
					m++;
				}
			}
		}
		printf("Case %d: %d\n", t, sol);
	}
	return 0;
}