Problem Statement

Given two arrays A & B of size N each. Find the maximum N elements from the sum combinations (Ai + Bj) formed from elements in array A and B.

For example if A = [1,2], B = [3,4], then possible pair sums can be 1+3 = 4 , 1+4=5 , 2+3=5 , 2+4=6 and maximum 2 elements are 6, 5

Example:

N = 4 a[]={1,4,2,3} b[]={2,5,1,6}

Maximum 4 elements of combinations sum are 10 (4+6), 9 (3+6), 9 (4+5), 8 (2+6)

Problem Link

Reference Link

K maximum sum combinations from two arrays - GeeksforGeeks

Code

vector<int> Solution::solve(vector<int> &A, vector<int> &B) {

    priority_queue<pair<int,pair<int,int>>> pq;

    set<pair<int,int>> s;
    vector<int> res;
    sort(A.begin(),A.end());
    sort(B.begin(),B.end());
    int n = A.size();
    
    pq.push({A[n-1]+B[n-1],{n-1,n-1}});

    s.insert({n-1,n-1});

    for(int count=0;count<n;count++)
    {
        auto p = pq.top();
        pq.pop();
        res.push_back(p.first);
   
        int i = p.second.first;
        int j = p.second.second;

        pair<int,int> p1 = {i-1,j};

        if(s.find(p1)==s.end())
        {
            s.insert(p1);
            pq.push({A[i-1]+B[j],{i-1,j}});
        }

        pair<int,int> p2 = {i,j-1};

        if(s.find(p2)==s.end())
        {
            s.insert(p2);
            pq.push({A[i]+B[j-1],{i,j-1}});
        }

    }
    return res;
}