如何返回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

这是一个递归生成器,可以生成所有有效的解决方案.与其他答案不同,此答案从不计算需要过滤的重复或无效字符串.这与前一个问题的答案中的算法几乎相同,但它不需要非递归辅助函数:

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

Answer 2

如果不必使用递归,这似乎工作:

from itertools import permutations

def valid(test):
  open, close = 0, 0
  for c in test:
    if c == '(':
      open += 1
    elif c == ')':
      close += 1
      if close > open:
        return False
  return True

def paren(n):
  perms = set(''.join(p) for p in permutations('(' * n + ')' * n))
  return [s for s in perms if valid(s)]