Problem 38: 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

题意：
对给出的n，从1到n里挑出一些数使它们的和等于没挑过的数字之和。求满足这样条件的组数。
代码如下：


/*
LANG: C
TASK: subset
*/
#include<stdio.h>
long long dp[40][400];
int main()
{
    freopen("subset.in", "r", stdin);
    freopen("subset.out", "w", stdout);
    int n, sum, i, j;
    scanf("%d", &n);
    sum = n * (n + 1);
    if ( sum / 2 & 1)//如果所有的和sum/2为奇数。就没有符合题意的。 
    {
        printf("0\n");
    }
    else
    {
        //dp[i,j]表示在前i个数里能组成和为j的组数 
        sum /= 4;
        dp[0][0] = 1;
        for (i = 1; i <= sum; i++)
        {
            dp[0][i] = 0;//因为下标最低为0.预先处理。 
        }
        for (i = 1; i <= n; i++)
        {
            for (j = 0; j <= sum; j++)
            {
                //dp[i,j]有两种组合情况，一种是前i-1个数里组成和为j的组数
                //一种是前i-1个数里组成和为j-i的组数，这样dp[i-1, j-i]加上j本身也是属于和为j的情况。 
                if (j < i)//确保j-i>=0 
                {
                    dp[i][j] = dp[i-1][j];
                }
                else
                {
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-i];
                }
            }
        }
        printf("%lld\n", dp[n][sum]/2);//因为是求出所有情况。所以要除二 
    }
    fclose(stdin);
    fclose(stdout);
    //system("pause");
    return 0;
}