# N max pair combinations

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)```
Method:

BFS.

Solution:

TIme: O(nlogn)
Space: O(n)

public class Solution {
static class Pair {
int i;
int j;
int val;

public Pair(int i, int j, int val) {
this.i = i;
this.j = j;
this.val = val;
}

@Override
public int hashCode() {
int hash = 17;
hash = hash * 13 + this.i;
hash = hash * 13 + this.j;
return hash;
}

@Override
public boolean equals(Object o) {
Pair p = (Pair) o;
return p.i == this.i && p.j == this.j;
}
}

public ArrayList<Integer> solve(ArrayList<Integer> A, ArrayList<Integer> B) {
PriorityQueue<Pair> maxHeap = new PriorityQueue<>(new Comparator<Pair>(){
@Override
public int compare(Pair a, Pair b) {
return Integer.compare(b.val, a.val);
}
});
Set<Pair> set = new HashSet<>();
ArrayList<Integer> result = new ArrayList<>();
Collections.sort(A, Collections.reverseOrder());
Collections.sort(B, Collections.reverseOrder());
Pair pair = new Pair(0, 0, A.get(0) + B.get(0));
while (result.size() < A.size()) {
Pair p = maxHeap.poll();
if (p.i + 1 < A.size()) {
Pair n = new Pair(p.i + 1, p.j, A.get(p.i + 1) + B.get(p.j));