# Find all combinations of 4 elements whose sum equals a target in Python

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

If there is better way for me to do it? it seems like the performace for the following code is too bad.

def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
from itertools import combinations
if len(nums) <= 3:return []
res, col = [], []
for i in combinations(nums, 4):
check = set(i)
if sum(i) == target and check not in col:
res.append(list(i))
col.append(check)
return res


Lists are pretty inefficient for this type of thing. The majority of the complexity is from iterating over the lists and comparing contents. Sets use a hash for their content, reducing complexity.

When using sets, most of the complexity comes from the combinations function.

Here are the results of a time test on your code

res1 = Solution().fourSum([-5,5,4,-3,0,0,4,-2],4)
print(time.time() - start)
# 0.0001342296600341797


The results of a method using only sets

res = Solution().fourSum([-5,5,4,-3,0,0,4,-2],4)
print(time.time() - start)
# 9.918212890625e-05


Code for the second function (updated to prevent 3-number outputs)

class Solution:
def fourSum(self, nums, target):
from itertools import combinations
res = set()
# Create all possible combinations

for i in combinations(nums, 4):
if sum(i) == target:
# Turns the tuple of numbers into list of strings
# Then joins them into a single string
# This allows hashing for the set
res.add(" ".join(sorted(list([str(x) for x in i]))))
# Splits the strings into lists of ints
return list([ [int(z) for z in x.split()] for x in res])

• (Never trust sub-second timing results without in-depth knowledge of and trust in the measurement mechanism. There are tools for micro-benchmarking.) – greybeard Dec 11 '18 at 12:42
• great information about using frozenset however, if it code correct? frozenset(i) will also filter the duplicated number? like i, target = (-5, 5, 0 ,0), 0  after frozenset(i) {-5,5 0} add into res? – A.Lee Dec 11 '18 at 16:03
• You're absolutely right, maybe someone has a better solution. In the meantime, I'll brainstorm. – Noah B. Johnson Dec 12 '18 at 1:15