SUBSUMS - Subset Sums

Problem Link

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

void computeSubsetSum(long long arr[], long long result[], int start, int len)
{
for(int i = 0; i < (1 << len); i++)
{
for(int j = 0; j < len; j++)
{
if(i & (1 << j))
{
result[i] += arr[start + j];
}

}
}
}

int main()
{
int n;
long long a, b;
long long arr[35];

cin >> n >> a >> b;

int size_lhs = 1 << (n / 2);
int size_rhs = 1 << (n - n / 2);

long long lhs[size_lhs];
long long rhs[size_rhs];

memset(lhs, 0, sizeof lhs);
memset(rhs, 0, sizeof rhs);

for(int i = 0; i < n; i++)
{
cin >> arr[i];
}

    /* Divide the set in 2 part n/ 2 element each
       and compute sum of subsets for both the part
       2^(n/2) + 2^(n / 2) < 2 ^n
    */
    computeSubsetSum(arr, lhs, 0, n / 2);
computeSubsetSum(arr, rhs, n / 2, n - n / 2);

    /* sort rhs so that can perform binary search on this */
sort(rhs, rhs + size_rhs);

long result = 0;

for(int i = 0; i < size_lhs; i++)
{
/* find lowest index such that lhs[i] + rhs[l] >= a
   find highest index such that lhs[i] + rhs[r] <= b
   sum with all index between l and r will be within range a, b
*/

int l = lower_bound(rhs, rhs + size_rhs, a - lhs[i]) - lhs;
int r = upper_bound(rhs, rhs + size_rhs, b - lhs[i]) - lhs;

result += (r - l);
}

cout << result << endl;

return 0;
}