[LC] 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:

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

Time: O(2^N)
Space: O(N)

 1 class Solution:
 2     def generateParenthesis(self, n: int) -> List[str]:
 3         res = []
 4         self.helper(0, 0, n, '', res)
 5         return res
 6     
 7     def helper(self, left, right, n, word, res):
 8         if left == n and right == n:
 9             res.append(word)
10         if left < n:
11             word += '('
12             self.helper(left + 1, right, n, word, res)
13             word = word[:-1]
14         if left > right:
15             word += ')'
16             self.helper(left, right + 1, n, word, res)
17             word = word[:-1]

Similar Solution 2:

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        cur = [''] * 2 * n
        self.helper(0, 0, 0, n, cur, res)
        return res
    
    def helper(self, left, right, level, n, cur, res):
        if left == n and right == n:
            word = ''.join(cur)
            res.append(word)
        if left < n:
            cur[level] = '('
            self.helper(left + 1, right, level + 1, n, cur, res)

        if left > right:
            cur[level] = ')'
            self.helper(left, right + 1, level + 1, n, cur, res)