How to approach Two Sets?

There are different ways to approach this question. I am presenting the greedy approach.

Assuming a is less than b, if not you can swap them to make it so.

Sort the given numbers.

We start checking from the smallest number x.

- First we see if b-x exists.If it does then both x and b-x will go to set B.(The reason we can say this with certainty is suppose a-x also exists and we assign x and a-x to the set A, then b-x will not be able to go set B as numbers are distinct and only one x exists, and for it to go to set A it will need a number smaller than x,(because a<b) but there is no such number(as we are considering the smallest number available). Thus we can say that if b-x exists, both x and b-x will be put in set B.
- After this the problem is easy. If b-x does not exist, check if a-x exist. If it does assign both x and a-x to set A. If it does not we can not divide the numbers in two sets as required.
- Continue the same with the remaining numbers.

@thunderking, Thanks for the approach. I am having doubt for this case:

x,x,a-x,b-x,b-x.

So A[0] = x;

A[1] = x;

A[2] = a-x;

A[3] = b-x;

A[4] = b-x;

Now suppose you sent element x,x,b-x,b-x to Set B. Then answer for the following case will be “NO”. Please correct me if I am wrong.

It is given in the problem statement that the all numbers are distinct, therefore this case never arises.

Thank you

suppose the array is {6,7} a=13 b=12. Then this approach will not give the correct answer. I think we need to handle the case when x=a/2 or x=b/2.

Another obvious approach could be by formulating the problem as a **perfect bipartite matching** problem and then use Hopcroft-Karp algorithm for solving it.

**How to identify it as a bipartite matching problem?**

It’s quite easy to make a note that the array needs to be split into 2 disjoint sets. This pretty much indicates that one can use bipartite matching algortihm.

**Why perfect?**

This part was easy enough to figure out as it was clearly mentioned in the problem:

He wants to divide

allof them into

two sets A and B

Hope that helps

@sikander_nsit if the array is {6,7} and a=13,b=12, then this approach will give the correct answer because as I have written in the explanation, we assume b is greater and if it is not, we swap A and B to make it so then both 6 and 7 will go to set B which is 13. This will also handle the case if x=a/2 or b/2 as we are trying to find a-x or b-x except x itself.

Thanks…got it.