Meet_in_the_Middle-An Intuitive Problem Solving Approach

Hello folks, after a steady response on my previous blog SWE/SDE Interviews Do’s and Don’ts over my medium channel, I write this blog to share a new problem solving approach that I learnt while solving problems on LeetCode.

Problem Link : Target Sum

Intuition : Considering this problem to be solved by Recursion (Brute Force) and then optimized by memoized solution (Dynamic Programming), I would like to bring into notice a very intuitive way of solving this problem using Meet_in_the_Middle technique & Bit manipulation.

Algorithm :

1. Think of brute force way of inserting ‘+’ or ‘-’ signs before different indices in the array. This would generally take upto O(2^N) computations — Time Complexity. (0≤N≤20)
2. Can you think of optimizing this by dividing array into two parts ? Quite similar to Divide and Conquer? Well, yes you are pretty close to the solution. This would not differ the complexity but the array size is directly reduced to half for applying above step over the left and right sub-arrays.
3. Well, now work with Bit manipulation over left and right sub-arrays and store the count of sums obtained in a Hash map or a dictionary.
4. Traverse over either leftDictionary or the rightDictionay to check whether the targetSum can be achieved from them and increment counter using the summition theme with the product of occurences obtained while achieving the targetSum.

Note : Meet_in_the_Middle technique is only applicable for the Aggregate Functions like sum, max,min , avg etc.

Below is my source code of implementation for this problem.

Solution Code :

#define umap unordered_map
#define vi vector<ll>
#define REP(i,a,b) for(ll i=a;i<b;i++)
typedef long long ll;
class Solution {
public:
    
    umap<ll,ll> getDicNums(vi nums){
        int size=nums.size();
        umap<ll,ll>countDic;
        
        ll i;
        REP(i,0,(1<<size)){
            
            ll times=0;
            ll ans=0;
            
            while(times<size){
                
                if(((1<<times)&i)!=0){
                    ans+=nums[times];   
                }
                else{
                    ans-=nums[times];
                }
                
                times++;
            }
            countDic[ans]++;
            
        }
        return countDic;
        
    }
    
    int findTargetSumWays(vector<int>& nums, int target) {
        
        int size=nums.size();
        
        if(size==1)
        {
            target=abs(target);
            nums[0]=abs(nums[0]);
            if(target==nums[0])
            {
                if(target==0)
                    return 2;
                return 1;
            }
            return 0;
            
        }
        
        ll mid=size/2;
        
        vi left,right;
        ll i;
        REP(i,0,mid){
            left.push_back(nums[i]);
        }
        REP(i,mid,size){
            right.push_back(nums[i]);
        }
        
        umap<ll,ll>leftDic=getDicNums(left);
        umap<ll,ll>rightDic=getDicNums(right);
        
        int count=0;
        for(auto ele:leftDic){
            if(rightDic.count(target-ele.first)!=0){
                count+=(ele.second*rightDic[target-ele.first]);
            }
        }
       return count;      
    }
};

More resource to learn : Gaurav Sen Video