給定一個整數 n
,請生成所有可能由 n
對括號組成的 有效括號組合。
範例 1:
Input: n = 3
Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]
範例 2:
Input: n = 1
Output: ["()"]
本題是經典的回溯問題,主要挑戰在於:
思路
程式碼實現 (Python)
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
result = []
def backtrack(current: str, open: int, close: int):
# 終止條件
if len(current) == 2 * n:
result.append(current)
return
# 如果可以添加左括號
if open < n:
backtrack(current + "(", open + 1, close)
# 如果可以添加右括號
if close < open:
backtrack(current + ")", open, close + 1)
# 開始回溯
backtrack("", 0, 0)
return result
時間與空間複雜度
思路
dp[i]
表示由 i
對括號組成的所有合法括號組合。i
,合法的組合可以表示為:程式碼實現 (Python)
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
dp = [[] for _ in range(n + 1)]
dp[0] = [""] # 0 對括號時,只有空字串
for i in range(1, n + 1):
for p in range(i):
q = i - 1 - p
for left in dp[p]:
for right in dp[q]:
dp[i].append(f"({left}){right}")
return dp[n]
時間與空間複雜度
思路
n
對括號組成的字符串組合(例如排列 2n
個括號的所有方式)。(
,balance + 1
;遇到右括號 )
,balance - 1
。程式碼實現 (Python)
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
from itertools import product
def is_valid(sequence: str) -> bool:
balance = 0
for char in sequence:
if char == "(":
balance += 1
else:
balance -= 1
if balance < 0:
return False
return balance == 0
# 生成所有可能的組合
all_combinations = product("()", repeat=2 * n)
result = ["".join(seq) for seq in all_combinations if is_valid(seq)]
return result
時間與空間複雜度
2^(2n)
,檢查有效性需要 O(n)。本題是經典的括號生成問題,最常用的方法是 回溯法,它結構清晰且效率高,能夠在有限的遞歸深度內生成所有合法組合。動態規劃法則適合於理解更為結構化的解法,暴力法則可作為基礎練習。