SPOJ Subset Sums (SUBSUMS), unexpected output

What’s wrong with my code?

problem: https://www.spoj.com/problems/SUBSUMS/
code: https://ide.codingblocks.com/s/75656

Short code, please have a look :slight_smile:

vi subsets(const vi &v){
vi ans;
int n=v.size();
for(int i=0;i<(1<<n);i++){
    int sum=0,j=0,I=i;
    while(I){
        if(I&1)sum+=v[j];
        j++;
        I>>=1;
    }
    ans.push_back(sum);
}
return ans;

}

signed main(){
FASTER;
int n,a,b;cin>>n>>a>>b;
int n1=n/2,n2=n-n1;
vi v1(n1),v2(n2),sv1,sv2;cin>>v1>>v2;//overloaded, no worries here
sv1=subsets(v1);
sv2=subsets(v2);
sort(all(sv2));
int ans=0;
for(int num:sv1)ans+=(upper_bound(all(v2),b-num)-lower_bound(all(v2),a-num));
cout<<ans<<"\n";
}

Solution/Reference: https://codinghangover.wordpress.com/2014/12/28/spojsubsums-subset-sums/

N will always be <=34/2, i have divided the array, used meet in the middle approach…

v2 is not sorted maybe. You are using lower_bound and upper_bound on v2.

1 Like

Perfect! that solved the problem. Thanks!!! search should have been on sv2…

What language was this code written in?

c++ :sweat_smile::joy: