7-4 子集和问题 (30分)

//和 7-6 部落卫队问题，背包问题 一样 
//对与每一层数（这里是每一个整数）都有两种选择，要或者不要 
// 就不写那么多注释了 

#include <bits/stdc++.h>
using namespace std;
int n; // n个正整数
int target; // 目标数
int arr[100000];
bool ifuse[100000]={0};
int PreTotal=0; 
bool solute = 0;
int sum=0;

void search(int dep)
{
    
    // 到达叶子节点或获得solution 
    if( dep > n || solute || PreTotal>target )   return;
    
    
    // 使用arr[dep] 
    if(PreTotal + arr[dep]<=target)
    {
       PreTotal = PreTotal + arr[dep];
       ifuse[dep]=1;
    
       if(PreTotal == target)  // 找到solution 
        {
           for(int i=1;i<=n;i++)
          {
             if(ifuse[i]) cout<<arr[i]<<" ";
          }
            solute = 1;
            exit(1); 
            return ;
        }  
    
         search(dep+1);
        PreTotal = PreTotal - arr[dep];
        ifuse[dep]=0;
    }
    
        
    //不使用arr[dep] 
    if(!solute)  search(dep+1);
    
    
    return ;
}



int main()
{
    cin>>n>>target;
    
    for(int i=1;i<=n;i++)
    {
        cin>>arr[i];
        sum=sum+arr[i];
    }
    
    //极端数据，target很大 
    if(sum<target) {
        cout<<"No Solution"<<endl;
        return 0;
    }
    
    search(1);
    
    if(!solute)  cout<<"No Solution"<<endl;
    
    return 0;
 }