Find all combinations of 4 elements whose sum equals a target in Python I wrote a solution to find all combinations of 4 elements from a list whose sum of elements equals some target


  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) &lt;= 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])