Hello Everyone,

I was trying to solve a problem in which I was given a set of number(in range 1-10^5 and size of set is at max 10^5). Task was to form the two disjoint sets from the given set such that sum of elements of each set is at least X(in range 1-10^5) and sum of size of both sets is minimized.

I tried a lot but could only come up with O(n^2) solution. Can anyone please suggest some idea on how to do it?

Note : Union of disjoint sets need not be the original set.

TIA

How about binary searching for the minimal sum of sizes? Clearly, if you can form such two sets with

kelements, you can also form two such sets with theklargest elements in your set.How will we apply binary search?

I think it's the same as this problem?

I could not understand the editorial so I was looking for alternate method or better explanation of the given method.

You might want to look at this post first. Subset sum DP is possible in O(NsqrtN).