# 22. Generate Parentheses

#### Difficulty: Medium
link: https://leetcode.com/problems/generate-parentheses/

### 1. Backtracking
#### $O(4^n/sqrt(n))$ runtime, $O(4^n/sqrt(n))$ space

如果只是要計算有幾種可能，那可以用DP解，但要列出所有情況的話，就要用backtracking。

這裡用函數dfs來做backtracking，設定終止條件和繼續走下去的條件。

每次有兩條路可以選擇，分別是左括號和右括號，path紀錄走過的路徑，left和right分別紀錄左括號和右括號累積的數量。

終止條件是path走到底有2n個左右括號。若左括號數量還未到上限n，還能繼續走左括號；若左括號數量比右括號多，還能繼續走右括號。

複雜度計算與Catalan number有關，可以參考Leetcode官方解法。

##### python

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        results = []
        
        def dfs(path, left, right):
            if len(path) == 2 * n:
                results.append(path)
                return
            
            if left < n:
                dfs(path + "(", left + 1, right)
            
            if right < left:
                dfs(path + ")", left, right + 1)
        
        dfs("", 0, 0)
        
        return results

### 2. Closure Number
#### $O(4^n/sqrt(n))$ runtime, $O(4^n/sqrt(n))$ space

神奇解法！

##### python

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        if n == 0: 
            return ['']
        
        ans = []
        for c in range(n):
            for left in self.generateParenthesis(c):
                for right in self.generateParenthesis(n-1-c):
                    ans.append('({}){}'.format(left, right))
        
        return ans

###### tags: `leetcode`