# Calculate Possibilities of Throwing a Coin N Times in Python

## The challenge

In this challenge, you will be given an integer n, which is the number of times that is thrown a coin. You will have to return an array of strings 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)

## The solution in Python code

Option 1:

``````from itertools import product

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

Option 2:

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

Option 3:

``````memo = {1 : ["H", "T"]}
for j in range(2, 18):
b = memo[j-1]
total = set()
for i in b:
``````test.describe("Basic Tests")