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

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)

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?

Answer 1

Here's a recursive generator that yields all valid solutions. Unlike the other answers, this one never calculates duplicated or invalid strings that need to be filtered out. This is pretty much the same algorithm as in this answer to a previous question, though it doesn't need a non-recursive helper function:

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

If it doesn't have to be done using recursion, this seems to work:

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)]

Answer 3

I am new to dynamic programming and recursion, but here is my solution without recursion. Please let me know why it wont work or if this is an acceptable solution:

class Parenthesis(object):
    def __init__(self, parens):
        self.parens = parens
        self.my_valid_parens = {
                                1: ['()'],
                                2: ['()()', '(())']
                               }

    def generate_valid_paren(self):
        if self.parens <= 2:
            return self.my_valid_parens[self.parens] 

        i = 3
        while i <= self.parens:
            new_set = []
            for each in self.my_valid_parens[i-1]:
                new_set += set([each + '()', '()' + each, '(' + each + ')'])
            self.my_valid_parens[i] = list(new_set)
            i += 1

if __name__ == '__main__':
    num = 4
    p = Parenthesis(num)
    p.generate_valid_paren()
    print p.my_valid_parens[num]

Here is my output for when num = 3 and 4 respectively:

3: ['(()())', '()()()', '()(())', '(())()', '((()))']

4: ['(()())()', '()(()())', '((()()))', '()()()()', '(()()())', '()()(())', '(()(()))', '()(())()', '((())())', '(())()()', '()(())()', '()((()))', '(((())))', '((()))()']