USACO 2.2.2 – Subset Sums

#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;

int main() {
	int n;
	freopen("subset.in", "r", stdin), freopen("subset.out", "w", stdout);
	scanf("%d", &n);
	long long int dp[400] = { 0 }, sum = (n * (n + 1))/2;
	dp[0] = 1;
	for (int i = 1; i <= n; i++)
		for (int s = sum/2; s >= i; s--)
			dp[s] += dp[s - i];

	printf("%lld\n", (sum%2? 0 : dp[sum/2] / 2));
	return 0;
}