Printing valid combination of parentheses in python

Question

I am trying to print all valid combination of parentheses in python using my own intuition. It almost worked but just that it doesn't print few combinations. The code looks like this

solution = ""

def parentheses(n):

    global solution

    if n == 0:
        print solution
        return

    for i in range(1, n+1):
        start_index = len(solution)
        solution = solution + ( "(" * i + ")" * i )
        parentheses(n - i)
        solution = solution[:start_index]

if __name__ == "__main__":
    n = int(raw_input("Enter the number of parentheses:"))
    print "The possible ways to print these parentheses are ...."
    parentheses(n)

For n = 3, it prints

( )( )( )
( )( ( ) )
( ( ) )( )
( ( ( ) ) )

It works like this.

In the first iteration

( )( )( ) will be printed, when the call returns to the immediate parent, it will slice of the list where it started to append first which will now be ( ) and run the next iteration of the loop to print ( )( ( ) ) and so on

The problem is I am somehow not able to capture this combination using this logic

( ( )( ) )

While I am thinking on how to fix it, if any python guru can suggest a fix to this, then that will be great. There are alternate solutions, but since I came very close, I want to improve mine.

Answer 1

I think your current version of the logic is a little oversimplified to capture all the possibilities.

This problem boils down to 3 different cases:

1. We've used all of our open parentheses and just need to close them
2. We don't have any currently open parentheses and need to add one before closing again
3. We've got at least one open and can either open a new one or close one.

To follow that logic, we then need to keep track of the number of open parens we have left to use (no below), the current string of parens, and the current balance of open vs. closed (curb below):

def parens(no, s="", curb=0):
    # case 1: all open parens used
    if no == 0: 
        if curb == 0: 
            return [s]
        return parens(no, s+")", curb-1) 

    # case 2: none are currently open
    if curb == 0:
        return parens(no-1, s+"(", curb+1)

    # case 3: one or more are currently open
    return parens(no-1, s+"(", curb+1) + parens(no, s+")", curb-1)

Answer 2

This seems like a natural use of memoization. parenthesis(10) will involve parentheses(6) and parentheses(4), but parentheses(9) will also involve parentheses(6) -- so parenthesis(6) should just be computed once. Also -- it is natural to use sets since that prevents e.g. ()()() from being counted twice, once as () + ()() and once as ()() + (). This leads to the following code, which either slaps a new pair of parentheses around parentheses generated for n-1 or concatenates the results of two previous calls:

cache = {}

def parentheses(n):
    if n == 0:
        return set([''])
    elif n in cache:
        return cache[n]
    else:
        par = set('(' + p + ')' for p in parentheses(n-1))
        for k in range(1,n):
            par.update(p+q for p in parentheses(k) for q in parentheses(n-k))
        cache[n] = par
        return par

For example,

>>> for p in parentheses(3): print(p)

(()())
((()))
()(())
()()()
(())()