In this kata you will be given an **integer n**, which is the number of times that is thown a coin. You will have to return an array of string for all the possibilities (heads[H] and tails[T]). Examples:
```coin(1) should return {"H", "T"}```
```coin(2) should return {"HH", "HT", "TH", "TT"}```
```coin(3) should return {"HHH", "HHT", "HTH", "HTT", "THH", "THT", "TTH", "TTT"}```
When finished sort them alphabetically.

In C and C++ just return a ```char*``` with all elements separated by```,``` (without space):
```coin(2) should return "HH,HT,TH,TT"```
INPUT:
```0 < n < 18```
Careful with performance!! You'll have to pass 3 basic test (n = 1, n = 2, n = 3), many medium tests (3 < n <= 10) and many large tests (10 < n < 18)

Difficulty: introductory

Starter code:

def coin(n):
	

Solutions:
from itertools import product

def coin(n):
    return list(map(''.join, product(*(["HT"]*n))))

from itertools import product

def coin(n):
    return list(map(''.join, product('HT', repeat=n)))

from itertools import product

def coin(n):
    return [''.join(xs) for xs in product('HT', repeat=n)]

def coin(n): return [x + v for x in coin(n-1) for v in 'HT'] if n - 1 else ['H','T']

from itertools import product

def coin(n):
    return [''.join(p) for p in product('HT', repeat=n)]

from itertools import product;coin=lambda n:list(map("".join,product(*(['HT']*n))))

import itertools
def coin(n):
    l=list(itertools.product("HT", repeat=n))
    return([''.join(list) for list in l])


def coin(n):
    f = f'{{:0{n}b}}'
    t = str.maketrans('01', 'HT')
    return [f.format(k).translate(t) for k in range(2**n)]

def coin(n):
    return gen_coin(n, "", [])
def gen_coin(n, solution, res):
    if n==0:
        res.append(solution)
    else:
        gen_coin(n-1, solution+"H", res)
        gen_coin(n-1, solution+"T", res)
    return res

def coin(n):
    return helper(n, "", [])

def helper(n, path, lst_of_ans):
    if n == 0:
        lst_of_ans.append(path)
        return lst_of_ans
    helper(n - 1, path + "H", lst_of_ans)
    helper(n - 1, path + "T", lst_of_ans)
    return lst_of_ans