➤ Problem Link : SUBSUMS
👉 Hint : edit please
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
ll n;
void calcSum(vector<ll> arr, vector<ll> &v)
{
ll m=arr.size();
for(ll i=0;i<pow(2,m);i++)
{
ll sum=0;
for(ll j=0;j<m;j++)
if(i & 1<<j)
sum+=arr[j];
v.pb(sum);
}
}
int main()
{
ll a,b;
cin>>n>>a>>b;
vector<ll> arr,arr2;
ll v;
for(int i=0;i<n/2;i++)
{
cin>>v;
arr.pb(v);
}
for(int i=n/2;i<n;i++)
{
cin>>v;
arr2.pb(v);
}
vector<ll> v1,v2;
v2.pb(LONG_MIN);
v2.pb(LONG_MAX);
calcSum(arr,v1);
calcSum(arr2,v2);
ll ans=0;
sort(v2.begin(),v2.end());
ll mx,mn,q;
for(ll val : v1)
{
mx=b-val;
mn=a-val;
auto it=upper_bound(v2.begin(),v2.end(),mx);
if(it==v2.begin())
continue;
it--;
auto it2=lower_bound(v2.begin(),v2.end(),mn);
it2--;
q=it-it2;
ans+=q;
}
cout<<ans;
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.