Tukukkk

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) <= 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(range(-25,25),0)

print(time.time() - start)

# 0.3020472526550293

The results of a method using only sets

res = Solution().fourSum(range(-25,25),0)

print(time.time() - start)

# 0.1206510066986084

Code for the second function

class Solution:

    def fourSum(self, nums, target):

        """

        :type nums: List[int]

        :type target: int

        :rtype: List[List[int]]

        """

        from itertools import combinations

        res = set()

        for i in combinations(nums, 4):

            check = set(i)

            if sum(i) == target:

                res.add(i)

        return list([list(x) for x in res])