22. Generate Parentheses

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

Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1
Output: ["()"]

Constraints:

• 1 <= n <= 8

---

p is the parenthesis-string built so far, left and right tell the number of left and right parentheses still to add, and parens collects the parentheses.

Solution 1

I used a few “tricks”… how many can you find? 🙂

def generateParenthesis(self, n):
    def generate(p, left, right, parens=[]):
        if left:         generate(p + '(', left-1, right)
        if right > left: generate(p + ')', left, right-1)
        if not right:    parens += p,
        return parens
    return generate('', n, n)

Solution 2

Here I wrote an actual Python generator. I allow myself to put the yield q at the end of the line because it’s not that bad and because in “real life” I use Python 3 where I just say yield from generate(...).

def generateParenthesis(self, n):
    def generate(p, left, right):
        if right >= left >= 0:
            if not right:
                yield p
            for q in generate(p + '(', left-1, right): yield q
            for q in generate(p + ')', left, right-1): yield q
    return list(generate('', n, n))

Solution 3

Improved version of this. Parameter open tells the number of “already opened” parentheses, and I continue the recursion as long as I still have to open parentheses (n > 0) and I haven’t made a mistake yet (open >= 0).

def generateParenthesis(self, n, open=0):
    if n > 0 <= open:
        return ['(' + p for p in self.generateParenthesis(n-1, open+1)] + \
               [')' + p for p in self.generateParenthesis(n, open-1)]
    return [')' * open] * (not n)