### qwerty29's blog

By qwerty29, history, 4 weeks 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;
}  Comments (2)
 » I changed your code a little bit and it got AC. Code#include #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 arr(n); for(int i=0;i> arr[i]; vector left, right; for(int i=0;i<(1< m; // for(int num : right) m[num]++; sort(all(right)); for(int i=0;i
•  » » hey, thanks! looks like binary search is faster than the hash map in c++, theoretically, hashmap should have performed better right?