Write a function which makes a list of strings representing all of the ways you can balance `n` pairs of parentheses

### Examples

```python
balanced_parens(0) => [""]
balanced_parens(1) => ["()"]
balanced_parens(2) => ["()()","(())"]
balanced_parens(3) => ["()()()","(())()","()(())","(()())","((()))"]
```

Difficulty: interview

Starter code:

def balanced_parens(n):
	

Solutions:
def balanced_parens(n): return list(dfs([],0,0,n))

def dfs(s, open, close, maxP):
    if close==maxP:
        yield "".join(s)
        return
    
    if open > close:
        s.append(')')
        yield from dfs(s,open,close+1,maxP)
        s.pop()
    
    if open < maxP:
        s.append('(')
        yield from dfs(s,open+1,close,maxP)
        s.pop()

def balanced_parens(n):
    def push_in(s, n1, n2):
        if n1 + n2 == n * 2: res.append(s); return
        if n1 < n          : push_in(s + '(', n1 + 1, n2)
        if n1 - n2 > 0     : push_in(s + ')', n1, n2 + 1)

    res = []; push_in('', 0, 0)
    
    return res

def balanced_parens(n):
    '''
    To construct all the possible strings with n pairs of balanced parentheses 
    this function makes use of a stack of items with the following structure:
        (current, left, right)
    Where:
        current is the string being constructed
        left is the count of '(' remaining
        right is the count of  ')' remaining
    '''
    stack = [('', n, 0)]
    result = []
    
    # Loop until we run out of items in the stack
    while stack:
        current, left, right = stack.pop()
        
        # if no '(' or ')' left to add, add current to the result
        if left == 0 and right == 0:
            result.append(current)
            
        # if we can, add a '(' and return to the stack
        if left > 0:
            stack.append((current + '(', left - 1, right + 1))
            
        # if we can, add a ')' and return to the stack    
        if right > 0:
            stack.append((current + ')', left, right - 1))
            
    return result

def balanced_parens(n):
    if n == 0:
        return [""]
    if n == 1:
        return ["()"]
    result = []
    for s in balanced_parens(n - 1):
        result += [s[:i]+"()"+s[i:] for i in range(0,len(s))]
    return list(set(result))

from functools import lru_cache

@lru_cache()
def balanced_binaries(n):
    return {0} if not n else \
        set.union(*({2 | x << 2, 1 << 2*n-1 | x << 1, 2 << 2*(n-1) | x} for x in balanced_binaries(n-1))) | \
        {a<<2*i | b for i in range(2, n-1) for b in balanced_binaries(i) for a in balanced_binaries(n-i)}

def balanced_parens(n, table=str.maketrans('10', '()')):
    return [bin(x).lstrip('0b').translate(table) for x in balanced_binaries(n)]

def balanced_parens(n):
    return parens(n, n)
    
def parens(o, c):
    return (['(' + e for e in parens(o - 1, c)] if o else []) + ([')' + e for e in parens(o, c - 1)] if c > o else []) or ['']

def balanced_parens(n):
    return list(set([p[:i] + "()" + p[i:] for p in balanced_parens(n - 1) for i in range(0, len(p))])) if n > 1 else ([""], ["()"])[n]

def balanced_parens(n):return rec(n,"(",list()) if n!=int() else [""]
def rec(n,current,ways):
    if n>current.count("("):
        ways=rec(n,current+"(",ways)
        if current.count("(")>current.count(")"):
            ways=rec(n,current+")",ways)
    else:ways+=[current+(n-current.count(")"))*")"]
    return ways

from functools import lru_cache

@lru_cache(maxsize=None)
def balanced_parens(n):
    if not n:
        return [""]
    r = set()
    for x in balanced_parens(n - 1):
        r.add("(" + x + ")")
    for i in range(1, n // 2 + 1):
        lo = balanced_parens(i)
        hi = balanced_parens(n - i)
        for x in lo:
            for y in hi:
                r.add(x + y)
                r.add(y + x)
    return list(r)

def balanced_parens(n):
    res = ['']
    for _ in range(n):
        res2 = set()
        for v in res:
            for p in range(len(v) if v else 1):
                res2.add(v[:p]+'()'+v[p:])
        res = list(res2)
    return res