題目描述
給定一個整數 n，請生成所有可能由 n 對括號組成的 有效括號組合。
範例 1：
Input: n = 3範例 2：
Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]
Input: n = 1
Output: ["()"]
解題思路
本題是經典的回溯問題，主要挑戰在於：
- 正確地生成所有組合。
- 確保生成的括號組合有效。
解法一：回溯法 (Backtracking)
思路
- 使用遞歸函數進行回溯：
- 當前生成的括號序列存儲在變量 current 中。
- open 表示目前已使用的左括號數量。
- close 表示目前已使用的右括號數量。
- 遞歸條件：
- 如果左括號的數量小於 n，則可以繼續添加左括號。
- 如果右括號的數量小於左括號，則可以繼續添加右括號。
- 終止條件：
- 當 current 長度等於 2 * n（即 n 對括號的總字符數），將 current 加入結果集。
- 使用回溯法逐步生成所有可能的組合，並通過條件檢查確保有效性。
程式碼實現 (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
時間與空間複雜度
- 時間複雜度：O(4^n / √n)
- 空間複雜度：O(n)
解法二：動態規劃 (Dynamic Programming)
思路
- 使用動態規劃的思想構造結果。
- 定義
dp[i]表示由i對括號組成的所有合法括號組合。 - 對於每個
i，合法的組合可以表示為： - 將 p 對括號組合包裹在一對括號中：("(" + dp[p] + ")" + dp[q])，其中 p + q = i - 1。
- 從小到大逐步計算所有組合。
程式碼實現 (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]
時間與空間複雜度
- 時間複雜度：O(4^n / √n)
- 空間複雜度：O(4^n / √n)
解法三：暴力生成 + 有效性檢查
思路
- 生成所有可能由
n對括號組成的字符串組合（例如排列2n個括號的所有方式）。 - 檢查每個組合是否有效，將有效的加入結果集。
- 檢查括號有效性：
- 從左到右遍歷字符串，用變量 balance 表示當前的括號平衡值。
- 遇到左括號
(，balance + 1；遇到右括號)，balance - 1。 - 如果在遍歷過程中 balance < 0，則字符串無效。
- 最終檢查 balance == 0，確保左右括號數量相等。
程式碼實現 (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
時間與空間複雜度
- 時間複雜度：O(2^(2n) * n)，生成所有排列需要
2^(2n)，檢查有效性需要 O(n)。 - 空間複雜度：O(2^(2n))，用於存儲所有可能的組合。
總結
本題是經典的括號生成問題，最常用的方法是 回溯法，它結構清晰且效率高，能夠在有限的遞歸深度內生成所有合法組合。動態規劃法則適合於理解更為結構化的解法，暴力法則可作為基礎練習。