HackerEarth Naruto's Punishment problem solution

In this HackerEarth Naruto’s Punishment problem solution Naruto went to watch a movie with his friends which turned out to be very boring. He decided to punish his friends with a problem for forcing him to watch such a boring movie.

There exists an array A consisting of N numbers. Output the number of subsets of the array A whose sum is greater than or equal to K.

Naruto’s friends being quite weak in coding were not able to solve this problem. Can you solve it for them and save them from Naruto’s Rasengan?

HackerEarth Naruto’s Punishment problem solution.

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <math.h>

#define ll long long int
#define maxN 100000
#define maxVal 100000000
#define minVal -100000000
#define mod 1000000007LL

#define gcd(a,b) __gcd(a,b)

using namespace std;

ll n,k,f;
ll a[45];
vector<ll> g[2];

void compute(ll t,ll i,ll s)
{
    if(i==f)
    {
        g[t].push_back(s);
        return;
    }
    compute(t,i+1,s+a[i]);
    compute(t,i+1,s);
}

ll searchb()
{
    ll s,e,m;
    s=0;
    e=(ll)g[1].size();
    while((e-s)>1)
    {
        m=s+(e-s)/2;
        if(g[1][m]>=f)
            e=m;
        else
            s=m+1;
    }
    if(g[1][s]>=f)
        return s;
    if(g[1][e]>=f)
        return e;
    return (ll)g[1].size();
}

int main()
{

    ll i,j,ans=0;
    cin>>n;
    for(i=0;i<n;i++)
        cin>>a[i];
    f=n/2;
    compute(0,0,0);
    sort(g[0].begin(),g[0].end());
    f=n;
    compute(1,n/2,0);
    sort(g[1].begin(),g[1].end());
    cin>>k;
    for(i=0;i<(ll)g[0].size();i++)
    {
        if(g[0][i]>=k)
            ans+=(ll)g[1].size();
        else
        {
            f=k-g[0][i];
            j=searchb();
            ans+=((ll)g[1].size()-j);
        }
    }
    cout<<ans;
    return 0;
}

coding problems solutions