pairs_sum.py

#!/bin/env python3

from collections import Counter

pairs = []

def find_pairs(A,x):
    V = {k:v for k,v in A.items() if k<=x}
    visited = []
    for i in V:
        if V[i]==0:
            continue
        c = x-i
        if c in V:
            visited.append(i)
            if c == i and V[c] > 1:
                pairs.append([c,i])
                V[c] -= 2
            else:
                pairs.append([c,i])
                V[c] -= 1
                V[A[i]] -= 1
    F = set(V.keys())-set(visited)
    for i in F:
        V[i] = 0
    Z = {k:v for k,v in V.items() if v==1}
    if Z:
        find_pairs(Z,x)
    else:
        return

x = [3,1,5,5,2,8,6]
find_pairs(Counter(x),10)

assert pairs == [[8, 2], [5, 5]]

# find all pairs (m,n) whose sum equals X, from a list of numbers (with duplicates)
# https://groups.google.com/forum/#!forum/dsa_sg

# In [62]: %timeit find_pairs([3,1,5,5,2,8,6,14],10)
# 100000 loops, best of 3: 8.07 µs per loop

from collections import Counter

def find_pairs(A, x):
    pairs = []
    A = [j for j in A if j<=x]
    V = Counter(A)
    for i in A:
        if V[i]==0:
            continue
        c = x-i
        if c in V:
            if c == i:
                if V[c] > 1:
                    pairs.append([c,i])
                    V[c] -= 2
            elif V[c] >= 1 and V[i] >= 1:
                pairs.append([c,i])
                V[c] -= 1
                V[i] -= 1
    return pairs

assert find_pairs([3,1,5,5,2,8,6,14],10) == [[5, 5],[8,2]]
assert find_pairs([1,1,1,1,1],2) == [[1, 1], [1, 1]]