USACO 2.2 - Subset Sums

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

출처: http://train.usaco.org/

1~N 까지의 연속된 자연수가 있다고 할 때, 이 수들을 두 개의 각 원소의 합이 같은 부분 집합으로 나눌 수 있다. N이 주어질 때 합이 같은 두 개의 부분 집합으로 나눌 수 있는 경우의 수를 구하시오.

Knapsack problem 와 비슷한 문제입니다.

두 개로 나누어진 부분집합의 합은 언제나 1~N 까지의 합의 절반 값이 되기 때문에 이 문제는 1~N 까지의 자연수를 조합하는 문제가 됩니다.

시간 복잡도를 줄이기 위해 dynamic programming 방법을 사용하였고 memoization을  위해 파라미터를 단순하게 integer 두 개로 만들었습니다.

remainder 는 합의 남은 수, curNum 은 현재 숫자로 사용하여 초기에 1~N 의 합 / 2 를 넣어주고 curNum 에 N을 넣은 후 curNum 을 1씩 차감하는 방법으로 routine 이 진행됩니다. 

my solving

c++

#include <fstream>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
 
int n;
int triangularNumber;
ll cache[400][40];
 
ll getNumWays(int remainder, int curNum)
{
    if (remainder < 0 || curNum < 0)
        return 0;
 
    ll& ret = cache[remainder][curNum];
    if (ret != -1)
        return ret;
 
    if (remainder == 0 && curNum == 0)
        return ret = 1;
 
    //in case of no sum + in case of sum
    return ret = getNumWays(remainder, curNum - 1) + getNumWays(remainder - curNum, curNum - 1);
}
 
int main()
{
    ifstream fin("subset.in");
    ofstream fout("subset.out");
 
    fin >> n;
    triangularNumber = n * (n + 1) / 2;
 
    memset(cache, -1, sizeof(cache));
 
    if (triangularNumber % 2 == 0)
        fout << getNumWays(triangularNumber / 2, n) / 2 << endl;
    else
        fout << "0" << endl;
 
 
    fin.close();
    fout.close();
    return 0;
}