1 files changed, 50 insertions, 0 deletions
diff --git a/2.2/subset.c b/2.2/subset.c
new file mode 100644
index 0000000..9f05b2c
--- /dev/null
+++ b/2.2/subset.c
@@ -0,0 +1,50 @@
+/*
+ID: mytbk921
+LANG: C
+TASK: subset
+*/
+
+#include <stdio.h>
+#include <stdlib.h>
+
+int main()
+{
+	FILE *fin = fopen("subset.in", "r");
+	FILE *fout = fopen("subset.out", "w");
+
+	long long dp[40][500];
+	int N, sum;
+	int i, j;
+	fscanf(fin, "%d", &N);
+	fclose(fin);
+
+	sum = N*(N+1)/2;
+	if (sum%2) {
+		fprintf(fout, "0\n");
+		fclose(fout);
+		return 0;
+	}
+	sum /= 2;
+
+	/* dp[x][y]: number of sets that sum of set is y 
+	 * with all numbers in the set <=x
+	 *
+	 * dp[k][0] = 1
+	 * dp[0][k] = 0 for k>0
+	 */
+	for (i=0; i<=N; i++)
+		dp[i][0] = 1;
+	for (i=1; i<=sum; i++)
+		dp[0][i] = 0;
+	for (i=1; i<=N; i++) {
+		for (j=1; j<=sum; j++) {
+			if (j<i)
+				dp[i][j] = dp[j][j];
+			else
+				dp[i][j] = dp[i-1][j] + dp[i-1][j-i];
+		}
+	}
+	fprintf(fout, "%lld\n", dp[N][sum]/2);
+	fclose(fout);
+	return 0;
+}