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
, 它输出 ['()()()', '(())()', '((()))']
遗漏'()(())'
.如何修改代码以正确输出所有可能的解决方案?
最佳答案
这是一个生成所有有效解决方案的递归生成器。与其他答案不同,这个答案从不计算需要过滤掉的重复或无效字符串。这与 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
关于python - 如何返回 n 对括号的所有有效组合?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20536523/