class Solution:
# @return a list of lists of length 4, [[val1,val2,val3,val4]]
def fourSum(self, num, target):
num.sort()
def ksum(num, k, target):
i = 0
result = set()
if k == 2:
j = len(num)  1
while i < j:
if num[i] + num[j] == target:
result.add((num[i], num[j]))
i += 1
elif num[i] + num[j] > target:
j = 1
else:
i += 1
else:
while i < len(num)  k + 1:
newtarget = target  num[i]
subresult = ksum(num[i+1:], k  1, newtarget)
if subresult:
result = result  set( (num[i],) + nr for nr in subresult)
i += 1
return result
return [list(t) for t in ksum(num, 4, target)]
A conise python solution based on ksum


Generator version:
def fourSum(self, num, target): num.sort() def ksum(num, k, target): i = 0 if k == 2: j = len(num)  1 while i < j: if num[i] + num[j] == target: yield (num[i], num[j]) i += 1 elif num[i] + num[j] > target: j = 1 else: i += 1 else: while i < len(num)  k + 1: newtarget = target  num[i] for sub in ksum(num[i+1:], k  1, newtarget): yield (num[i],) + sub i += 1 return [list(t) for t in set(ksum(num, 4, target))]

your algorithm is very good. I like them very much. Your idea is different from mine, my idea is 2Sum + 2Sum = 4Sum. But I think your idea is better, because yours is more general. Moreover, generator was used in your code of version 2, inspired by this, I think I should begin to learn python more deeply.