題目出處
難度
medium
題目分類
String, Dynamic Programming, Backtracking
2026-10-02 二刷
個人範例程式碼 - 二刷 (2026/10/02)
class Solution:
def generateParenthesis(self, n: int) -> list[str]:
ans = []
def dfs(remain_left, unmatched, path):
if len(path) == 2 * n:
ans.append("".join(path))
return
# 放 '('
if remain_left > 0:
path.append('(')
dfs(remain_left-1, unmatched+1, path)
path.pop()
# 放 ')'
if unmatched > 0:
path.append(')')
dfs(remain_left, unmatched-1, path)
path.pop()
dfs(n, 0, [])
return ans
算法說明
combination 的基礎題型，基本上就是考驗 DFS 與 backtracking 的使用。
Time Complexity
O(4^n)
遞迴深度為 2n (左右兩側括弧), 每層最多兩個分支, 結果是 2^(2n)
註：2^(2n) = 4^n，如果只回答 2^n 會低估
Space Complexity
O(n) # 遞回深度長度 O(2n) = O(n)
Boundary conditions
2022-06-16 一刷
個人範例程式碼 - 一刷 (2022/06/16)
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
ans = []
self.dfs(n, n, "", ans)
return ans
def dfs(self, left, right, current_str, ans):
# end of recursion
if left == 0:
for _ in range(right):
current_str += ")"
ans.append(current_str)
return
# define and split
if left >= 0:
self.dfs(left-1, right, current_str + "(", ans)
if right > left: # (3, 2), (3, 1)
self.dfs(left, right-1, current_str + ")", ans)
return
最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解
算法說明
用 dfs 把所有狀況窮舉出來，我們以 left, right 代替左右括弧剩餘的數量，
可新增 left 的條件：left > 0
可新增 right 的條件：right > left # (3, 2), (3, 1)
終止條件：left = 0，放上所有剩餘的 right
input handling
一同在 dfs 內處理，基本上是處理 n = 0 的情況
Boundary conditions
用 dfs 控制範圍，終止條件為當 left = 0