UVA 624 - CD

#include<bits/stdc++.h>
#define READ freopen("input.txt","r",stdin);
using namespace std;
typedef long long ll;
int target,n,ary[50];
vector<int>temp,res;
void call(int i,int sum,int c)
{
    if(i>=n)
    {
        int s=0,s2=0;
        for(int i=0; i<temp.size(); i++)
            s+=temp[i];
        for(int i=0; i<res.size(); i++)
            s2+=res[i];
        if(s>=s2)
        {
            if(s==s2)
            {
                if(temp.size()>res.size())
                    res=temp;
            }
            else
                res=temp;
        }
        return ;
    }
    if(sum+ary[i]<=target)
    {
        temp.push_back(ary[i]);
        call(i+1,sum+ary[i],c+1);
        temp.pop_back();
        c--;
    }
    else
        call(i+1,sum,c);
    call(i+1,sum,c);
}
int main()
{
    while(scanf("%d %d",&target,&n)==2)
    {
        temp.clear();
        res.clear();
        for(int i=0; i<n; i++)
            scanf("%d",&ary[i]);
        call(0,0,0);
        int s=0;
        for(int i=0; i<res.size(); i++)
        {
            s+=res[i];
            printf("%d ",res[i]);
        }
        printf("sum:%d\n",s);
    }
    return 0;
}