[LeetCode] Challenge log 22

Posted on |
22. Generate Parentheses

Analysis: DFS problem. Keep track of number of left and right parenthesis that is available. Either add a left or a right to next DFS level.

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:

1
2
3
4
5
6
7
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]
Soulution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """
        if n == 0: return []
        
        def recur(s, res, left, right):
            if left == 0 and right == 0: 
                res.append(s)
                return
            elif left < 0 or right < 0: 
                return
            
            recur(s + '(', res, left - 1, right + 1)
            recur(s + ')', res, left, right - 1)
                
        res = []
        recur('', res, n, 0)
        return res
0%