2
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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])
\$\endgroup\$
  • 2
    \$\begingroup\$ (Never trust sub-second timing results without in-depth knowledge of and trust in the measurement mechanism. There are tools for micro-benchmarking.) \$\endgroup\$ – greybeard Dec 11 '18 at 12:42
  • \$\begingroup\$ 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? \$\endgroup\$ – A.Lee Dec 11 '18 at 16:03
  • \$\begingroup\$ You're absolutely right, maybe someone has a better solution. In the meantime, I'll brainstorm. \$\endgroup\$ – Noah B. Johnson Dec 12 '18 at 1:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.