### qwerty29's blog

By qwerty29, history, 2 years ago,

You are given an array of n numbers. In how many ways can you choose a subset of the numbers with sum x?

Solution: Using meet in the middle approach but its timing out for few test cases, could you please help me where I can improve my code.

#include <bits/stdc++.h>
#define all(c) (c).begin(), (c).end()
#define present(c, x) ((c).find(x) != (c).end())
#define cpresent(c, x) (find(all(c),x) != (c).end())
#define fi first
#define se second
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define parr(arr) for(int num : (arr)) cout << num << ' '; cout << '\n';
using namespace std;

int main(){
ios::sync_with_stdio(false); cin.tie(NULL);
int n; cin >> n;
long long int x; cin >> x;
int mid = n/2;
vector<int> arr(n);
for(int i=0;i<n;++i) cin >> arr[i];
vector<long long int> left, right;
for(int i=0;i<(1<<mid);++i){
long long int sum = 0;
for(int j=0;j<32;++j){
if(i & (1<<j)){
sum += arr[j];
}
}
left.push_back(sum);
}
int rem = n-mid;
for(int i=0;i<(1<<rem);++i){
long long int sum =0;
for(int j=0;j<32;++j){
if(i & (1<< j))
sum += arr[mid+j];
}
right.push_back(sum);
}
long long int count = 0;
unordered_map<long long int,int> m;
for(int num : right) m[num]++;
for(int i=0;i<left.size();++i){
if(left[i] <= x){
long long int other = x - left[i];
count += m[other];
}
}
cout << count << '\n';
return 0;
}

• -1

| Write comment?
 » 4 months ago, # |   0 use custom hash function.
•  » » 3 months ago, # ^ |   0 what is this ?
•  » » » 3 months ago, # ^ |   0 you can create your own unordered_map which will work in O(n) and will not be colliding .
 » 3 months ago, # |   0 just use map instead of unordered
•  » » 3 months ago, # ^ |   0 It is tle btw
 » 3 months ago, # |   0 Reserve memory. Use m.reserve(1e6).Also, you can use custom hash. Blog: https://codeforces.com/blog/entry/62393