python - 如何返回 n 对括号的所有有效组合？

Question

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)

以上代码是我尝试解决上述问题的尝试。它为 n<3 提供了足够的解决方案, 但除此之外，它并没有给出所有的解决方案。例如，当 n=3 , 它输出 ['()()()', '(())()', '((()))']遗漏'()(())' .如何修改代码以正确输出所有可能的解决方案？

Answer 1

这是一个生成所有有效解决方案的递归生成器。与其他答案不同，这个答案从不计算需要过滤掉的重复或无效字符串。这与 this answer to a previous question 中的算法几乎相同。 ，尽管它不需要非递归辅助函数:

def paren(left, right=None):
    if right is None:
        right = left  # allows calls with one argument

    if left == right == 0: # base case
        yield ""

    else:
        if left > 0:
            for p in paren(left-1, right): # first recursion
                yield "("+p

        if right > left:
            for p in paren(left, right-1): # second recursion
                yield ")"+p