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

Example 1:

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

Example 2:

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

Constraints:

• 1 <= n <= 8

Related Topics: String Dynamic Programming Backtracking

## 解題邏輯與實作

1. 長度為 2n，且左括號（open parenthesis）個數等於右括號（close parenthesis）個數
這個條件應該是可以輸出正確形式的中止條件，所以這個終止時需要回傳正確的形式。但實作時，我不想多傳入常數 n（因為這個數在遞迴過程中不會變），所以我把條件給反過來使用倒數的方式：「當左括號剩餘個數為零，且右括號剩餘個數亦為零」時終止。

2. 右括號剩餘個數少於左括號剩餘個數
假設 n = 3，若目前字串為 ()) ，則左括號剩餘個數則為 2、右括號剩餘個數為 1，遇到這樣的非法形式就直接返回不處理了。

1. 若左括號個數仍有剩餘，即不為 0，則輸出一左括號後繼續向下遞迴。
2. 若右括號剩餘個數大於左括號剩餘個數，則輸出一右括號後繼續向下遞迴。

 12345678910111213141516171819 class Solution: def generateParenthesis(self, n: int) -> List[str]: results = [] cur_str = "" self.generate(cur_str, n, n, results) return results def generate(self, cur_str: str, open_remaining: int, close_remaining: int, results:list): if open_remaining == 0 and close_remaining == 0: results.append(cur_str) return if close_remaining < open_remaining: return if open_remaining > 0: self.generate(cur_str + "(", open_remaining-1, close_remaining, results) if close_remaining > open_remaining: self.generate(cur_str + ")", open_remaining, close_remaining-1, results) 

Runtime 大約 38 ms，約在 78.88% 左右，我再多加個終止條件試試應該可以加快速度：

 123456789101112131415161718192021222324 class Solution: def generateParenthesis(self, n: int) -> List[str]: results = [] cur_str = "" self.generate(cur_str, n, n, results) return results def generate(self, cur_str: str, open_remaining: int, close_remaining: int, results:list): if open_remaining == 0 and close_remaining == 0: results.append(cur_str) return if open_remaining == 0 and close_remaining > 0: cur_str += ')'*close_remaining results.append(cur_str) return if close_remaining < open_remaining: return if close_remaining < 0 or open_remaining < 0: return if open_remaining > 0: self.generate(cur_str + "(", open_remaining-1, close_remaining, results) if close_remaining > open_remaining: self.generate(cur_str + ")", open_remaining, close_remaining-1, results) 

Runtime 有稍微提升來到了 31 ms，約在 95.25% 左右。

## 更新紀錄

• 2023-02-15 發布
• 2023-01-09 完稿
• 2023-01-09 起稿