子集和问题

#include<bits/stdc++.h>
using namespace std;
bool used[1005];
int sum=0;//解的个数
int n,c,s=0;//和 
int a[1005],b[1005];//后缀和

void dfs(int i)
{
	if(sum>0)//找到了 
		return;
	if(s+b[i]<c)//提前结束 
		return;
	if(s==c)
	{
		for(int j=1;j<=n;j++)
		{
			if(used[j])//usd[i]&&sum==0
				cout<<a[j]<<" ";
		}
		sum++;
		return;
	}
	if(i>n)
		return;
	if(s+a[i]>c)//used[i]=false;
	{
		dfs(i+1);
		return;
	}
	s+=a[i];
	used[i]=true;
	dfs(i+1);
	
	s-=a[i];
	used[i]=false;
	dfs(i+1);
	return;
}

int main()
{
	cin>>n>>c;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	b[n]=a[n];
	for(int i=n-1;i>=1;i--)
		b[i]=a[i]+b[i+1];
	dfs(1);
	if(sum==0)
		cout<<"No Solution!";	
    return 0;
}