# 2.2.2 Subset Sums 集合

2.2.2 Subset Sums 集合

{3} and {1,2}

{1,6,7} and {2,3,4,5} {注 1+6+7=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}

``7``

``4``

``````/*
ID: supersnow0622
PROG: test
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <string>
#include<memory.h>
using namespace std;
int half;
long long c1[500],c2[500],c[500];
int main() {
ofstream fout ("test.out");
ifstream fin ("test.in");
int N,sum;
cin>>N;
sum=(1+N)*N/2;
if(sum%2!=0)
cout<<0;
else
{
half=sum/2;
c1[0]=c1[1]=1;

for(int i=2;i<=N;i++)
{
memset(c2,0,sizeof(c2));
memset(c,0,sizeof(c));
c2[0]=c2[i]=1;
for(int j=0;j<=half;j++)
{
c[j+0]+=c1[j]*c2[0];
c[j+i]+=c1[j]*c2[i];
}
for(int k=0;k<=half;k++)
c1[k]=c[k];
}
cout<<c1[half]/2;
}
return 0;
}
``````

``````/*

*/
#include <iostream>

using namespace std;

long long dp[10000];
int n,Max;
int main()
{
int i,j;
cin>>n;
Max=n*(n+1)/2;
if(Max&1)  //若总和为奇数，则不存在划分方案，输出0
cout<<0<<endl;
else
{
Max/=2;  //输出结果应除以2，因为互补的结果导致重复
dp[0]=1;
/*状态转移方程为f(i,j)=f(i-1,j-i)+f(i-1,j)(j>=i),其边界条件为
f(i,0)=1(i=1,2,...,N),f(i,j)的意义为1,2,...,i可以有多少种方式组成和为j的集合
*/
for(i=1;i<=n;++i)
for(j=Max;j>=i;--j)
dp[j]+=dp[j-i];
cout<<dp[Max]/2<<endl;
}
return 0;
}
``````