def paren(n):
    lst = ['(' for x in range(n)]
    current_string = ''.join(lst)
    solutions = list()
    for i in range(len(current_string)+1):
        close(current_string, n, i, solutions)
    return solutions

def close(current_string, num_close_parens, index, solutions):
    """close parentheses recursively"""
    if num_close_parens == 0:
        if current_string not in solutions:
            solutions.append(current_string)
        return
    new_str = current_string[:index] + ')' + current_string[index:]
    if num_close_parens and is_valid(new_str[:index+1]):
        return close(new_str, num_close_parens-1, index+1, solutions)
    else:
        return close(current_string, num_close_parens, index+1, solutions)

def is_valid(part):
    """True if number of open parens >= number of close parens in given part"""
    count_open = 0
    count_close = 0
    for paren in part:
        if paren == '(':
            count_open += 1
        else:
            count_close += 1
    if count_open >= count_close:
        return True
    else:
        return False

print paren(3)

El código anterior es mi intento de resolver el problema indicado. Da soluciones suficientes paran<3, pero por lo demás, no da todas las soluciones. Por ejemplo, cuandon=3, da salida['()()()', '(())()', '((()))'] dejando fuera'()(())'. ¿Cómo modifico el código para generar correctamente todas las soluciones posibles?