算法1

(01背包) $O(n^2)$

由于两个子集中的和相等且只能选择一次，选择任意的数拼成1+..n的和的一半。可以用01背包解决。

f[i][j]表示选了i个物品且体积是j
f[i][j]=f[i-1][j]+f[i-1][j-v]//选了i个物品且用去j个体积的方案=第i个物品选了的方案数+第i个物品没选的方案数

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=1e3;

int n,sum;
int f[N][N];
int mid;
int a[N];

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) sum+=i;
    if(sum%2) {cout<<"0";return 0;}

    for(int i=1;i<=n;i++) a[i]=i;

    mid=sum/2;
    f[0][0]=1;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=mid;j++)
    {
        f[i][j]+=f[i-1][j];
        f[i][j]+=f[i-1][j-a[i]];
    }

    cout<<f[n][mid];
    return 0;
}