twoSum to find all the possible unique couples

Question

I have such a problem

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

Note:

The solution set must not contain duplicate couples.

Example:

Given nums = [4, 7, 6, 3, 5], target = 10

because   4+ 6= 7+ 3   = 10
return  [[4, 6], [7,3]]

My solution:

class SolutionAll: #Single Pass Approach 
    def twoSum(self, nums, target) -> List[List[int]]:
        """
        :type nums: List[int]
        :type target: int
        """
        nums.sort()
        nums_d:dict = {}
        couples = []

        if len(nums) < 2:
            return []

        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i-1]: continue #skip the duplicates

            complement = target - nums[i]

            if nums_d.get(complement) != None:
                couples.append([nums[i], complement])          
            nums_d[nums[i]] = i                            
        return couples 

TestCase Results:

target: 9 
nums: [4, 7, 6, 3, 5]
DEBUG　complement: 6
DEBUG　nums_d: {3: 0}
DEBUG　couples: []
DEBUG　complement: 5
DEBUG　nums_d: {3: 0, 4: 1}
DEBUG　couples: []
DEBUG　complement: 4
DEBUG　nums_d: {3: 0, 4: 1, 5: 2}
DEBUG　couples: [[5, 4]]
DEBUG　complement: 3
DEBUG　nums_d: {3: 0, 4: 1, 5: 2, 6: 3}
DEBUG　couples: [[5, 4], [6, 3]]
DEBUG　complement: 2
DEBUG　nums_d: {3: 0, 4: 1, 5: 2, 6: 3, 7: 4}
DEBUG　couples: [[5, 4], [6, 3]]
result: [[5, 4], [6, 3]]
.
target: 2 
nums: [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1]
DEBUG　complement: 2
DEBUG　nums_d: {0: 0}
DEBUG　couples: []
DEBUG　complement: 1
DEBUG　nums_d: {0: 0, 1: 9}
DEBUG　couples: []
result: []

The solution works with [4, 7, 6, 3, 5] but failed with [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1]

I tried to remove the duplicates but get an unexpected results.

How could solve the problem with this one Pass solution?

Answer 1

The problem with your code is that it skips duplicate numbers, not duplicate pairs. Because of the

if i > 0 and nums[i] == nums[i-1]: continue #skip the duplicates

your code never tries to sum 1 + 1 = 2.

---

Here's a working solution with O(n) complexity:

from collections import Counter

def two_sum(nums, target):
    nums = Counter(nums)  # count how many times each number occurs

    for num in list(nums):  # iterate over a copy because we'll delete elements
        complement = target - num

        if complement not in nums:
            continue

        # if the number is its own complement, check if it
        # occurred at least twice in the input
        if num == complement and nums[num] < 2:
            continue

        yield (num, complement)

        # delete the number from the dict so that we won't
        # output any duplicate pairs
        del nums[num]

>>> list(two_sum([4, 7, 6, 3, 5], 10))
[(4, 6), (7, 3)]
>>> list(two_sum([0, 0, 0, 1, 1, 1], 2))
[(1, 1)]

---

See also:

• collections.Counter
• What does the "yield" keyword do?

Answer 2

Not sure what's wrong with your solution (and not sure what's right with it either), but you can achieve this easily in a "pretty-pythonic" manner:

def func(nums,target):
    return [(a,b) for a in nums for b in nums if a+b == target]

It assumes that two tuples which differ only by the order of elements are unique, and that an element can be used twice in the same tuple. If the definitions of the question are otherwise, then you can filter those tuples out of the returned value.

Answer 3

edited: see discussion below.

from itertools import combinations

list(set([(a,b) for a,b in combinations(sorted(nums),2) if a+b == target]))

This will remove duplicates as well.

Answer 4

Other version:

>>> nums = [4, 7, 6, 3, 5]
>>> target = 9 
>>> set((a, target-a) for a in nums if target-a in set(nums))
{(4, 5), (5, 4), (3, 6), (6, 3)}

For every element a of nums, if target-a in also in nums, we have:

• a + target-a = target (obvious);
• a and target-a are both in nums.

Since we loop over every a, we get all the solutions.

To get rid of the duplicates (x, y) and (y, x):

>>> set((a, target-a) for a in nums if 2*a<=target and target-a in set(nums))
{(4, 5), (3, 6)}

Because 2*a <= target is equivalent to a <= target-a. When a > target-a and the requested conditions are met, we have a previous b = target-a so that (b, target-b) is a solution.