Two Sets
Problem Link In this problem, we must divide a set of numbers into two sets such that if number x goes into set A, then the number A – x must also be put into set a and similarly, if number x is put into set b, then the number b – x must also be put into set b. If we had to actually go about assigning numbers to either set A or set b and then checking if the conditions above have been met, it would take way too long. This is because for each number we have two choices: put it in set a or put it in set b. This yields a time complexity of O(2n) which easily TLEs with n <= 1e5. There are some numbers that can go in either set if both the numbers A – x and B – x exist. There are also some numbers that can only be placed in set A since the number A – x exists in the array but not B – x and the same goes for numbers that can only be placed in only set B. there are also number that can’t be put in set A or B since neither of the numbers A – x and B – x exist. In this case, the numb...