[ create a new paste ] login | about

Link: http://codepad.org/DyGrYfdP    [ raw code | fork ]

iamyeasin - C++, pasted on Oct 18:
#include<bits/stdc++.h>
#define pf printf
#define sf scanf

using namespace std;

int arr[1234], ans[1234];
bool taken[1234]= {0};
int flag = 0,till=0,closest_sum=0;

void subBack(int idx, int t, int n,int sum1){
    if(sum1 == n && !flag){
        for(int i=0; i<idx; i++){
            pf("%d ",ans[i]);
        }
        pf("sum:%d\n",sum1);
        flag = 1;
        return;
    }

    if(idx >= t) {
            till = idx-1;
        return;
    }

    for(int i=idx; (i<n && !flag); i++){
        if(arr[i] + sum1 <= n && !taken[i] && !flag){
            taken[i] = 1;
            sum1 += arr[i];
            ans[idx] = arr[i];
            subBack(idx+1, t, n, sum1);
            sum1 -= arr[i];
        }
       // taken[i] = false;
    }

}


int main(){

//    std::ios_base::sync_with_stdio();
//    cin.tie(NULL);

    //freopen("in.txt", "rt", stdin);
    //freopen("outt.txt", "wt", stdout);

    int n,t;
    while( sf("%d",&n) != EOF){
        sf("%d",&t);
        memset(arr,0,sizeof(arr));
        memset(taken,0,sizeof(taken));
        memset(ans,0,sizeof(ans));

        int sum1=0,sum2=0;
        for(int i=0; i<t; i++){
            sf("%d",&arr[i]);
            sum2 += arr[i];
        }
        if(sum2 <= n){
            for(int i=0; i<t; i++){
                pf("%d ",arr[i]);
            }
            pf("sum:%d\n",sum2);
            continue;
        }

        subBack(0, t, n, 0);
        if(!flag){
             for(int i=0; i<till; i++){
                pf("%d ",ans[i]);
                closest_sum = 0;
                closest_sum += ans[i];
            }
            pf("sum:%d\n",closest_sum);
        }
        flag= 0;

    }


    return 0;
}


Create a new paste based on this one


Comments: