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;
}