# 子集和问题

``````5 10
2 2 6 5 4``````

``2 2 6``

``````#include<cstdio>
int a[10005];
int n,tar;
int vis[10005];
int flag,now;
void print()
{
for(int i=0;i<n;i++)
if(vis[i])
printf("%d ",a[i]);
}
void dfs(int k)
{
if(flag)
return;
for(int i=0;i<=n;i++)
{
if(vis[i]==0&&now+a[i]<=tar)
{
if(flag)
return;
now+=a[i];
vis[i]=1;
if(now==tar)
{
flag=1;
print();
return;
}
else dfs(k+1);
now-=a[i];
vis[i]=0;
}
}
}
int main()
{
long long int sum=0,t=0;;
scanf("%d %d",&n,&tar);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
sum+=a[i];
}
if(sum<tar)
{
printf("No Solution!");
return 0;
}
dfs(0);
if(flag==0)
printf("No Solution!");
return 0;
}``````

``````
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
int n,c,a[10000],b[10000],d[10000],i,sum=0;
bool pd;

void print(int dep)
{
int j;
for (j=1;j<=dep;++j)
printf("%d ",d[j]);
printf("\n");
return;
}

void dfs(int dep)
{
int r;
if (pd==1) return;
for (r=1;r<=n;++r)
if (!b[r]&&c-a[r]>=0)
{
if (pd==1) return;
c-=a[r];
d[dep]=a[r];
b[r]=1;
if (c==0)
{
if (pd==0)
print(dep);
pd=1;
return;
}
else dfs(dep+1);
if (pd==1) return;
c+=a[r];
b[r]=0;
}
}

int main()
{
scanf("%d%d",&n,&c);
for (i=1;i<=n;++i)
{
scanf("%d",&a[i]);
sum+=a[i];
}
if (sum<c)
{
printf("No Solution!\n");
return 0;
}
memset(d,0,sizeof(d));
memset(b,0,sizeof(b));
pd=0;
dfs(1);
if (!pd) printf("No Solution!\n");
return 0;
}

``````