menu

[LeetCode] 022. Generate Parentheses

Problem (Medium)

022. 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:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

Note:

  • the number of elements given n, is the “Catalan Number”, the n-th Catalan number $\frac{1}{n+1}\left(\begin{array}{c} 2n \ n \end{array}\right)$, which is bounded asymptotically by $\frac{4^n}{n\sqrt{n}}$.

Approach 1: Brute Force

Idea

Generate all possible cased ($2^{2n}$) and then check if each one is valid.

Solution

class Solution1:
    def generateParenthesis(self, n): 
        """ 
        :type n: int
        :rtype: List[str]
        """
        def generate(A=[]):
            if len(A) == 2*n:
                if valid(A):
                    res.append(''.join(A))
            else:
                A.append('(')
                generate(A)
                A.pop()
                A.append(')')
                generate(A)
                A.pop()

        def valid(A):
            bal = 0 
            for c in A:
                if c == '(': bal += 1
                else: bal -= 1
                if bal < 0: return False
            return bal == 0
        res = []
        generate()
        return set(res)

Complexity

  • Time: $O(2^{2n}n)$
  • Space: $O(2^{2n}n)$

Approach 2: Bachtracking

Idea

Instead of enumerating every possible case, only add them when we know it’s a valid sequence.

Solution

class Solution(object):
    def generateParenthesis(self, n): 
        """ 
        :type n: int
        :rtype: List[str]
        """
        def recurse(cur, left, right, res=[]):
            if left:
                recurse(cur+'(', left-1, right)
            if right > left:
                recurse(cur+')', left, right-1)
            if not right: 
                res.append(cur)
            return res 
        return set(recurse('', n, n))

Complexity

  • Time: $O(\frac{4^n}{n\sqrt{n}})$
  • Space: $O(\frac{4^n}{n\sqrt{n}})$



KF

Comments