How to return all valid combinations of n-pairs of parentheses?

user_1815412 0
Viewed 6690
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)

The above code is my attempt at solving the stated problem. It gives sufficient solutions for n<3, but otherwise, it doesn't give out all the solutions. For example, when n=3, it outputs ['()()()', '(())()', '((()))'] leaving out '()(())'. How do I modify the code to output all the possible solutions correctly?

backtracking recursion python
7 Answers

Here is my solution

from itertools import permutations
n = 3
input = ("( " * n) + (") " * n)
in_list = [f for f in input.split(" ") if f]
possible_combinations = list(permutations(in_list, n*2))
valid_list = []

def ret_valid(el):
    num_open = num_close = 0
    for val in el:
        if val == "(":
            num_open += 1
        else:
            num_close += 1
        if num_close > num_open:
            return False
    return True

for el in possible_combinations:
    if ret_valid(el):
        if "".join(el) not in valid_list:
            valid_list.append("".join(el))
print(", ".join(valid_list))
user_38812390
Related