Subset Sums

Subset Sums JRM
For many sets of consecutive integers from 1 through N (1 <= N <= 39), one can partition the set into two sets whose sums are identical.
For example, if N=3, one can partition the set {1, 2, 3} in one way so that the sums of both subsets are identical:

{3} and {1,2}

This counts as a single partitioning (i.e., reversing the order counts as the same partitioning and thus does not increase the count of partitions).
If N=7, there are four ways to partition the set {1, 2, 3, ... 7} so that each partition has the same sum:

{1,6,7} and {2,3,4,5}

{2,5,7} and {1,3,4,6}

{3,4,7} and {1,2,5,6}

{1,2,4,7} and {3,5,6}

Given N, your program should print the number of ways a set containing the integers from 1 through N can be partitioned into two sets whose sums are identical. Print 0 if there are no such ways.
Your program must calculate the answer, not look it up from a table.

PROGRAM NAME: subset

INPUT FORMAT

The input file contains a single line with a single integer representing N, as above.

SAMPLE INPUT (file subset.in)

7

OUTPUT FORMAT

The output file contains a single line with a single integer that tells how many same-sum partitions can be made from the set {1, 2, ..., N}. The output file should contain 0 if there are no ways to make a same-sum partition.

SAMPLE OUTPUT (file subset.out)

4

동적 이동 방정식: j=i일 때 dp[i][j]=dp[i-1][j]+dp[i-1][j-i];pp[i][j]는 전 i--1개수의 전제에서 전 i개수는 j의 개수로 모을 수 있음을 나타낸다.dp[i-1][j]는 전 i-1개수를 j로 모을 수 있는 개수를 나타내고, dp[i-1][j-i]는 전 i-1개수의 합을 토대로 i개수를 더하면 j로 모을 수 있는 개수를 나타낸다.두 개를 합치면 앞의 i개수를 모아서 j를 만들 수 있는 총 개수다.
/* ID:hanzhic1 PROG:subset LANG:C++  */ #include #include #include using namespace std; int dp[40][400]; void subdp(int n,int sum) {     int i,j;     dp[1][1] = 1;     for(i = 2;i<=n;i++)     { for(j = 1;j<=sum;j++) {    dp[i][j] = dp[i-1][j];    if((j-i)>0)    { dp[i][j]+=dp[i-1][j-i];    } }     } } int main() {     ifstream fin("subset.in");     ofstream fout("subset.out");     int n;     int ans;     int sub;     fin>>n;     memset(dp,0,sizeof(dp));     sub = n*(1+n)/2;     ans = 0;     if(sub%2==0)     { subdp(n,sub/2); ans = dp[n][sub/2];     }     fout<Compiling... Compile: OK Executing... Test 1: TEST OK [0.000 secs, 3232 KB] Test 2: TEST OK [0.000 secs, 3232 KB] Test 3: TEST OK [0.000 secs, 3232 KB] Test 4: TEST OK [0.000 secs, 3232 KB] Test 5: TEST OK [0.000 secs, 3232 KB] Test 6: TEST OK [0.000 secs, 3232 KB] Test 7: TEST OK [0.000 secs, 3232 KB] All tests OK.

Your program ('subset') produced all correct answers! This is your submission #6 for this problem. Congratulations!

Here are the test data inputs:

------- test 1 ----
7
------- test 2 ----
15
------- test 3 ----
24
------- test 4 ----
31
------- test 5 ----
36
------- test 6 ----
39
------- test 7 ----
37