python - Find four numbers in a list that add up to a target value -

below code wrote in attempt solve problem: find 4 numbers in list add x.

def sum_of_four(mylist, x):     twosum = {i+j:[i,j] in mylist j in mylist}     4 = [twosum[i]+twosum[x-i] in twosum if x-i in twosum]     print 4 sum_of_four([2, 4, 1, 1, 4, 6, 3, 8], 8) 

the answer sample input is:

[[1, 1, 3, 3], [1, 2, 3, 2], [3, 1, 3, 1], [3, 2, 1, 2], [3, 3, 1, 1]] 

however, list of lists contains duplicates. example, [1,1,3,3] same [3,3,1,1].

how can print list of lists without duplicate lists? want efficient possible in runtime , space. possible change list comprehension don't print duplicates? not want sort lists , use set() delete duplicates. want better.

a correct , relatively efficient approach starts counting number of times each value occurs in input list. suppose value occurs count times. can append count copies of value list in build selection of values. before appending copies of value, , after appending each copy, make recursive call move on next value.

we can implement approach follows:

length = 4  # requires frequencies list of (value, count) sorted value. def doit(frequencies, index, selection, sum, target, selections):   if index == len(frequencies):     return   doit(frequencies, index + 1, selection[:], sum, target, selections)  # skip value.   value, count = frequencies[index]   in range(count):     selection.append(value)     sum += value     if sum > target:       return  # quit because remaining values can bigger.     if len(selection) == length:       if sum == target:         selections.append(selection)       return  # quit because selection can longer.     doit(frequencies, index + 1, selection[:], sum, target, selections)  # use these values.  def sum_of_length(values, target):   frequency = {}   value in values:     frequency[value] = frequency.setdefault(value, 0) + 1   frequencies = sorted(frequency.items())  # sorting allows more efficient search.   print('frequencies:', frequencies)   selections = []   doit(frequencies, 0, [], 0, target, selections)   return list(reversed(selections))  print(sum_of_length([2, 4, 1, 1, 4, 6, 3, 8], 8)) print(sum_of_length([1, 1, 1, 2, 2, 3, 3, 4], 8)) print(sum_of_length([-1, -1, 0, 0, 1, 1, 2, 2, 3, 4], 3)) 

by way, correct answer sample input [[1, 1, 2, 4]]. there 1 way select 4 elements [2, 4, 1, 1, 4, 6, 3, 8] such sum 8.