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]+new_num[pair] in twoSums: twoSums[new_num[pair]+new_num[pair]].append(pair) else: twoSums[new_num[pair]+new_num[pair]]=[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<pair2] for comb in combinations: results.add(tuple([new_num[i] for i in comb])) return [list(sums) for sums in results]
Yes there is.
The general optimum for k-sum is O(n^(k/2)lg(k)). But there are special cases for some even k's to run faster.
Refer to this question:
Roll down to my answer. the OP's algorithm is very smart, but as it need to sort, it was actually O(n^2lg(n)). Mine does not sort, it should be O(n^2)
I agree with you "there are special cases for some even k's to run faster". That is the reason I post the question here. However, you need to show it is O(n^2). The gap is that it is hard to analyze how many elements in the hashtable (key: list of pairs) and how many elements in the list of pairs given a key value. As a consequence, in your code the size of combinations is not clear (combinations=[pair1+pair2 for pair1 in twoSums[num1] for pair2 in twoSums[num2]]). Actually I think in the worst case, your code is O(N^4). Let's say that num has 2N elements of N -1s and N 1s, target is 0.
Then we have 3 keys, -2,0, and 2. Just take key 2 and -2 for example. There are O(N^2) pair1s and O(N^2) pair2s which lead to O(N^4) pair1+pair2. Correct me if I am wrong.
I was well aware of the problem you raised. And that's why I said we could refine the algorithm by first filtering off excessive repeating elements. We don't need those repeat to be more than 4 times. I just did not take the time to do the refinement in my own code, but I did mention it.
remove the duplicate elements from the input list, not from the pairs. You don't need the same element appearing more than 4 times in the input list. That is O(N)
I think you are right after filtering the repeating elements down to 4. Would you update your answer?
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.