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
,它输出['()()()', '(())()', '((()))']
离开了'()(())'
。如何修改代码以正确输出所有可能的解决方案?
这是一个产生所有有效解决方案的递归生成器。与其他答案不同,这个答案从不计算需要过滤掉的重复或无效字符串。这与中的算法几乎相同这是对上一个问题的回答 https://stackoverflow.com/a/728051/1405065,尽管它不需要非递归辅助函数:
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
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)