Jak zwrócić wszystkie prawidłowe kombinacje n-par nawiasów?
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)
Powyższy kod jest moją próbą rozwiązania zadanego problemu. Daje wystarczające rozwiązania dlan<3
, ale poza tym nie podaje wszystkich rozwiązań. Na przykład kiedyn=3
, to wychodzi['()()()', '(())()', '((()))']
pomijając'()(())'
. Jak zmodyfikować kod, aby poprawnie wyprowadzić wszystkie możliwe rozwiązania?