Условия легко сводятся к таким: Дано число 1 ≤ n ≤ 105 и n целых чисел 1 ≤ ai ≤ n, 
Нужно разбить их на две группы с одинаковой суммой и вывести разбиение или сказать, что это невозможно.
Условия очень похожи на рюкзак, но я умею решать эту задачу только жадно. В разборе написано, что задачу можно решить каким-то рюкзаком за 
.
Линк на Разбор и на Условия (задача C)
Надеюсь, вы поможете мне решить эту задачу. :]
An approach would be:
Do a knapsack where the limit of the knapsack would be half the total sum of the elements. If the result yields exactly half the total sum, it means that there is a subset that sums to this half. And, obviously, if there is one that sums to half the total sum, there is another one that sums to the other half.
I know this is approach doesn't have the complexity you asked... I'm curious to know about it too...
Note: number of different values of a[i] is O(sqrt(N)) because sum is equal to 2 * n.
That's exactly what I was looking for.
Implemented it in C++, worked totally fine. Even though you had some typos in your solution, I've got your point.
Big thanks to you! :]