The Ulam sequence `U` is defined by `u0 = u`, `u1 = v`, with the general term `uN` for `N > 2` given by the least integer expressible uniquely as the sum of two distinct earlier terms. In other words, the next number is always the smallest, unique sum of any two previous terms.

Complete the function that creates an Ulam Sequence starting with the given `u0` and `u1`, and contains `n` terms.

## Example

The first 10 terms of the sequence `U(u0=1, u1=2)` are: 1, 2, 3, 4, 6, 8, 11, 13, 16, 18.

Let's see it in details:
* The first term after the initial 1, 2 is obviously 3, because 1 + 2 = 3
* The next term is 1 + 3 = 4 (we don't have to worry about 4 = 2 + 2 since it is a sum of a *single term* instead of *distinct terms*)
* 5 is not a member of the sequence since it is representable in two ways: 1 + 4 and 2 + 3
* 6 is a memeber, as 2 + 4 = 6
* etc.


Description Reference: http://mathworld.wolfram.com/UlamSequence.html

---

Performance version: https://www.codewars.com/kata/ulam-sequences-performance-edition

Difficulty: introductory

Starter code:

def ulam_sequence(u0, u1, n):
	

Solutions:
from itertools import combinations
from collections import defaultdict

def ulam_sequence(u0, u1, n):
    seq = [u0, u1, u0 + u1]
    
    while len(seq) < n:
        candidates = defaultdict(int)
        
        for a, b in combinations(seq, 2):
            candidates[a + b] += 1
        
        for num, pairs in sorted(candidates.items()):
            if num > seq[-1] and pairs == 1:
                seq.append(num)
                break
    
    return seq

import collections



def ulam_sequence(u0, u1, n):
    possible_sums={}
    
    sequence = [u0, u1]
    
    for _ in range(0,n-2):
        for term in sequence[:-1]:
            if term+sequence[-1] in possible_sums.keys():
                possible_sums[term+sequence[-1]] += 1
            else:
                possible_sums[term+sequence[-1]] = 1
        possible_sums = collections.OrderedDict(sorted(possible_sums.items()))
        next_term = min([sum for sum in possible_sums.keys() if possible_sums[sum]==1 and sum not in sequence])
        sequence.append(next_term)
        
    return sequence

def ulam_sequence(u0, u1, n):
    seq = [u0, u1]
    for _ in range(n - 2):
        sums = sorted([seq[i] + seq[j] for i in range(len(seq)) for j in range(i, len(seq)) if i != j])
        seq.append(next(s for s in sums if sums.count(s) == 1 and s not in seq))
    return seq

from collections import Counter
from itertools import combinations

def ulam_sequence(u0, u1, n):
    seq = [u0, u1]
    for i in range(n - 2):
        c = Counter(a + b for a, b in combinations(seq, 2))
        x = min(key for key in c if key > seq[-1] and c[key] == 1)
        seq.append(x)
    return seq

import itertools

def ulam_sequence(u0, u1, n):
    arr=[u0,u1]
    temp=u0+u1
    control=list(map(sum, list(itertools.combinations(arr,2))))
    while(len(arr)!=n):
        if(control.count(temp)==1):
            arr.append(temp)
            control=list(map(sum, list(itertools.combinations(arr,2))))
        temp+=1
    return arr

from collections import Counter

def ulam_sequence(u0, u1, n):

    seen, lst = {u0,u1}, [u0,u1]
    while len(lst) < n:
    
        c = Counter(v+w for i,v in enumerate(lst) for w in lst[i+1:] if v+w not in seen)
        cnd = min(filter(lambda kv: kv[1]==1, c.items()),
                  key=lambda kv: kv[0])[0]
                  
        lst.append(cnd)
        seen.add(cnd)
        
    return lst

def ulam_sequence(u0, u1, n):
    """
    Input
    u0 = first number
    u1 = second numberr
    n  = number of elements in sequence
    
    Return
    Ulam Sequence (u0, u1, u2...) with n-terms
    """
    U = [u0, u1]
    next_num = u1 + 1
    while len(U) < n:
        count = 0
        index = 0
        for number in U:
            if next_num - number in U and number != next_num/2:
                count += 1
            if count >= 3:
                break
        if count < 3 and count > 0:
            U.append(next_num)
        next_num += 1
    return U

ulam_sequence=f=lambda u,v,n,l=set():v and(l.clear()or l.update({u,v}))or len(l)>=n and sorted(l)or l.add(next(y for y in range(max(l)+1,2*max(l))if sum(2*x<y and y-x in l for x in l)==1))or f(0,0,n,l)

def isCandidate(x, seq):
    count = 0
    left_pointer = 0
    right_pointer = len(seq) - 1
    
    while left_pointer < right_pointer:
        left = seq[left_pointer]
        right = seq[right_pointer]
        
        if left + right == x:
            count += 1
            if count == 2:
                return False
        
        if left + right > x:
            right_pointer -= 1
            left_pointer = 0
            continue
            
        left_pointer += 1
        
    return count == 1

def ulam_sequence(u0, u1, n):
    seq = [u0, u1]
    x = u0 + u1
    while len(seq) < n:
        if isCandidate(x, seq):
            seq.append(x)        
        x += 1
    return seq

def ulam_sequence(U,V,Q) :
    R = [U,V]
    S = [U + V]
    while len(R) < Q :
        while 1 < len(S) and S[-1] == S[-2] :
            T = S.pop()
            while T == S[-1] : S.pop()
        T = S.pop()
        S.extend(T + V for V in R)
        R.append(T)
        S.sort(reverse = True)
    return R