The general k-sum problem is discussed here http://cs.stackexchange.com/questions/2973/generalised-3sum-k-sum-problem. The optimal solution is said to be O(N^(K/2) logN) in general for even K.

I understand for some special cases there are faster solutions but I have seen not a single solution in the discuss which is O(N^2) (even some are claimed to be O(N^2)).

Please answer this question after you checked the following case:

Num has 2N elements of N -1s and N 1s. Target is 0.

I modified @Chomolungma code which I think is O(N^2). After removing the number of repeating elements to at most 4, the size of duplicates can be bounded by a constant which leads to O(N^2).

```
class Solution:
# @return a list of lists of length 4, [[val1,val2,val3,val4]]
def fourSum(self, num, target):
results=set()
num.sort()
new_num=[]
filter=dict()
for x in num:
if x not in filter:
filter[x]=1
new_num.append(x)
elif filter[x]<4:
filter[x]+=1;
new_num.append(x)
pairs=[[x,y] for x in xrange(len(new_num)) for y in xrange(x+1,len(new_num))]
twoSums=dict()
for pair in pairs:
if new_num[pair[0]]+new_num[pair[1]] in twoSums:
twoSums[new_num[pair[0]]+new_num[pair[1]]].append(pair)
else:
twoSums[new_num[pair[0]]+new_num[pair[1]]]=[pair]
for num1 in twoSums:
num2=target-num1
if num2 >= num1 and num2 in twoSums:
combinations=[pair1+pair2 for pair1 in twoSums[num1] for pair2 in twoSums[num2] if pair1[1]<pair2[0]]
for comb in combinations:
results.add(tuple([new_num[i] for i in comb]))
return [list(sums) for sums in results]
```