def bf_find_closest_triplet(sample, target):
    res = 10000000
    triplet = []
    for i in range(len(sample)):
        for j in range(len(sample)):
            for k in range(len(sample)):
                if i != j and i != k and j != k:
                    s = sample[i] + sample[j] + sample[k]
                    if abs(s-target) < res:
                        res = abs(s-target)
                        triplet = [sample[i], sample[j], sample[k]]
    return res, triplet

def find_closest_triplet(sample, target):
    d = Counter(sample)
    merge_sort(sample)
    i = 0
    j = len(sample)-1
    while i < j:
        s = sample[i] + sample[j]
        d[sample[i]] -= 1
        d[sample[j]] -= 1
        third_num = target - s
        print(sample[i], sample[j], "difference =",s, "third_num = ", third_num)
        if third_num in d and d[third_num] > 0:
            return [sample[i], sample[j], third_num]
        else:
            d[sample[i]] += 1
            d[sample[j]] += 1
            if third_num < 0:
                j -= 1
            else:
                i += 1

for _ in range(100):
    n = rand.randrange(0, 20)
    sample = [rand.randrange(-20, 20) for _ in range(n)]
    target = rand.randrange(-50, 50)
    res, triplet = bf_find_closest_triplet(sample, target)
    if res == 0:
        print("Sample = ", sample)
        print("Target = ", target)
        print("Brute force:", triplet)
        print("My solution:", find_closest_triplet(sample, target))
        print()