624 - CD

Author: Ismail Hosen

Daffodil International University

Problem Link

//Please follow from Main function

#include<bits/stdc++.h>

using namespace std;



string toBinary(int n){

    string s="";

    while(n){

        s+=(n%2)+'0';

        n/=2;

    }

    return s;

}



int main()

{

    string ans;

    int N, T, Min, subset, sum, len, dif;

    while(cin>>N){

        cin>>T;

        int arr[T];

        for(int i=0; i<T; i++)cin>>arr[i];

        Min=N+5, subset = pow(2, T);

        for(int i=0; i<subset; i++){

            string s=toBinary(i);

            sum=0, len=s.size();

            for(int j=len; j<T; j++) s+='0';

            for(int j=0; j<len; j++) if(s[j]=='1') sum+=arr[j];

            dif = N-sum;

            if(dif>=0 && dif<=Min){

                //cout<<s<<" Dif: "<<dif<< " " <<sum<<" Min: "<<Min<<endl;

                ans=s;

                Min=dif;

            }

        }



        int sum=0;

        for(int i=0; i<ans.size(); i++){

            if(ans[i]=='1'){

                cout<<arr[i]<<' ';

                sum+=arr[i];

            }

        }

        cout<<"sum:"<<sum<<endl;

    }

    return 0;

}