22. Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[ “((()))”, “(()())”, “(())()”, “()(())”, “()()()” ]

Tree-ish structure of the solution

We need to generate all valid parentheses with n pairs of parentheses, so the beginning of every valid parenthesis is (. This is like the root of a tree, we then “grow” the tree based on what can we stick under the root.

Grow the tree

At each level of the tree, we can grow the tree based on the partial parenthesis formed from root to the current node. At the root level, we the partial parenthesis is ( and given n = 3, we can grow to () or ((.

Growing length

We grow the tree along certain node until the length formed from root to that leaf is 2 * n.

Growing Criteria

At each leaf, we can extend the tree with a (, or a ) or stop extending.
We can extend ( when the number of ( in the path is less than n.
We can extend ) when there are unmatched ( in the path.

Recursion

We will create a recursive function that create path. It will judge the existed partial path and determine how to recurse. It will return the path if the length of the path is already 2 * n.

    def generateParenthesis(self, n):
        """
        recursive
        """
        sol = []
        def recur(num_left, num_open_left, path):
            if len(path) == 2 * n:    
                sol.append(path)

            if num_left > 0:
                recur(num_left - 1, num_open_left + 1, path + '(')

            if num_open_left > 0:
                recur(num_left, num_open_left - 1, path + ')')

        recur(n, 0, '')
        return sol

Iterative, using dynamic programming

Only three possibilities to add parenthesis

To maintain the parenthesis valid, we can only add in pair and build on valid parenthesis with shorten length. For example, we want to build a valid parenthesis with length n, we must start off with a valid parenthesis of length n – 2.

Given a valid parenthesis of length n – 2, there are only two ways to add parenthesis that forms a valid parenthesis of length n. For the sake of convenience, let’s call the solution of valid parenthesis of length n – 2 f(n – 1).
1: Add parenthesis to enclose f(n – 1) :'(‘ + f(n – 1) + ‘)’.
2: Add () to the left of f(n – 1)
3: Add () to the right of f(n – 1).

But this will cause problem if f(n – 1) contains symmetric parenthesis. Then 2 and 3 will produce duplicate.

Get ride of case 3 so there will be no duplicate

We need to have n pairs of parenthesis in a solution. We can break up it into a single pair of parenthesis and two groups of valid parenthesis that sum up to n – 1.
The two groups of valid parenthesis will be solution of smaller n. Let them be solution for n = i and n = j.

The first parenthesis has to be ‘(‘ and then we can add either ‘)’ or sol[i]. Then we will add sol[j].
We will iterate all possible i ( i = 0… n – 1) and all possible j ( j = n – i – 1… 0) to append to solution of n.

This solves the duplicate problem.
BTW we need a base case.

We can form the solution of n = 2 by making change the solution of n = 1.
For n = 1, sol = “()”. And for n = 2, the sol is [“()()”, “(())”]. Abstractly:
f(0): “”

f(1): “(“f(0)”)”

f(2): “(“f(0)”)”f(1), “(“f(1)”)”

f(3): “(“f(0)”)”f(2), “(“f(1)”)”f(1), “(“f(2)”)”

So f(n) = “(“f(0)”)”f(n-1) , “(“f(1)”)”f(n-2) “(“f(2)”)”f(n-3) … “(“f(i)”)”f(n-1-i) … “(f(n-1)”)”

    def generateParenthesis(self, n):
        """
        iterative
        """
        dp = [[] for i in range(n + 1)]
        dp[0].append('')
        for i in range(n + 1):
            for j in range(i):
                dp[i] += ['(' + x + ')' + y for x in dp[j] for y in dp[i - j - 1]]
        return dp[n]

Sorry the definition of solution is not clear in the text.

Catalan

Yeah the length of the sol is Catalan number.
We noticed the first few Catalan number is 1,1,2,5,14…
Just like the recursive formula in Math, our code need to start iterating at n = 0.

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax