【洛谷】P1466 集合 Subset Sums

【洛谷】P1466 集合 Subset Sums 题目地址：

https://www.luogu.com.cn/problem/P1466

题目描述：
对于从 1 ∼ n 1sim n 1∼n的连续整数集合，能划分成两个子集合，且保证每个集合的数字和是相等的。举个例子，如果 n = 3 n=3 n=3，对于 { 1 , 2 , 3 } {1,2,3} {1,2,3}能划分成两个子集合，每个子集合的所有数字和是相等的： { 3 } {3} {3}和 { 1 , 2 } {1,2} {1,2}是唯一一种分法（交换集合位置被认为是同一种划分方案，因此不会增加划分方案总数）。如果 n = 7 n=7 n=7，有四种方法能划分集合 { 1 , 2 , 3 , 4 , 5 , 6 , 7 } {1,2,3,4,5,6,7 } {1,2,3,4,5,6,7}，每一种分法的子集合各数字和是相等的：
{ 1 , 6 , 7 } {1,6,7} {1,6,7}和 { 2 , 3 , 4 , 5 } {2,3,4,5} {2,3,4,5}
{ 2 , 5 , 7 } {2,5,7} {2,5,7}和 { 1 , 3 , 4 , 6 } {1,3,4,6} {1,3,4,6}
{ 3 , 4 , 7 } {3,4,7} {3,4,7}和 { 1 , 2 , 5 , 6 } {1,2,5,6} {1,2,5,6}
{ 1 , 2 , 4 , 7 } {1,2,4,7} {1,2,4,7}和 { 3 , 5 , 6 } {3,5,6} {3,5,6}

给出 n n n，你的程序应该输出划分方案总数。

输入格式：
输入文件只有一行，且只有一个整数 n n n。

输出格式：
输出划分方案总数。

数据范围：
对于 100 % 100% 100%的数据， 1 ≤ n ≤ 39 1le n le 39 1≤n≤39。

先求 s = 1 + 2 + . . . + n s=1+2+...+n s=1+2+...+n，如果 s s s是奇数则不存在方案，否则即求 s / 2 s/2 s/2被 1 , 2 , . . . , n 1,2,...,n 1,2,...,n表示为和的方案数除以 2 2 2（划分有对称性），这可以用 0 − 1 0-1 0−1背包问题的做法来做。设 f [ i ] [ j ] f[i][j] f[i][j]是只考虑 1 ∼ i 1sim i 1∼i这些数的情况下，和为 j j j的组合方案数，那么 f [ 0 ] [ 0 ] = 1 , f [ 0 ] [ . > 0 ] = 0 f[0][0]=1,f[0][.>0]=0 f[0][0]=1,f[0][.>0]=0。按照 i i i这个数取不取可以分类，如果不取，有 f [ i − 1 ] [ j ] f[i-1][j] f[i−1][j]种方案，如果取，有 f [ i − 1 ] [ j − i ] f[i-1][j-i] f[i−1][j−i]种方案。所以有： f [ i ] [ j ] = f [ i − 1 ] [ j ] + f [ i − 1 ] [ j − i ] f[i][j]=f[i-1][j]+f[i-1][j-i] f[i][j]=f[i−1][j]+f[i−1][j−i]考虑空间优化，每行从大到小遍历即可。代码如下：

#include 
using namespace std;

const int N = 39 * 40 / 2 + 10;
int n, s;
long f[N];

int main() {
    scanf("%d", &n);
    s = n * (n + 1) / 2;
    if (s % 2 != 0) puts("0");
    else {
        f[0] = 1;
        for (int i = 1; i <= n; i++)
            for (int j = s / 2; j >= i; j--)
                f[j] += f[j - i];

        printf("%d", f[s / 2] / 2);
    }

    return 0;
}

时间复杂度 O ( n 3 ) O(n^3) O(n3)，空间 O ( n 2 ) O(n^2) O(n2)。