[LeetCode解題攻略] 22. Generate Parentheses

更新於 發佈於 閱讀時間約 8 分鐘

題目描述

給定一個整數 n,請生成所有可能由 n 對括號組成的 有效括號組合


範例 1:

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

範例 2:

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


解題思路

本題是經典的回溯問題,主要挑戰在於:

  1. 正確地生成所有組合。
  2. 確保生成的括號組合有效。

解法一:回溯法 (Backtracking)

思路

  1. 使用遞歸函數進行回溯:
    • 當前生成的括號序列存儲在變量 current 中。
    • open 表示目前已使用的左括號數量。
    • close 表示目前已使用的右括號數量。
  2. 遞歸條件:
    • 如果左括號的數量小於 n,則可以繼續添加左括號。
    • 如果右括號的數量小於左括號,則可以繼續添加右括號。
  3. 終止條件:
    • 當 current 長度等於 2 * n(即 n 對括號的總字符數),將 current 加入結果集。
  4. 使用回溯法逐步生成所有可能的組合,並通過條件檢查確保有效性。

程式碼實現 (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)

思路

  1. 使用動態規劃的思想構造結果。
  2. 定義 dp[i] 表示由 i 對括號組成的所有合法括號組合。
  3. 對於每個 i,合法的組合可以表示為:
    • 將 p 對括號組合包裹在一對括號中:("(" + dp[p] + ")" + dp[q]),其中 p + q = i - 1。
  4. 從小到大逐步計算所有組合。

程式碼實現 (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)

解法三:暴力生成 + 有效性檢查

思路

  1. 生成所有可能由 n 對括號組成的字符串組合(例如排列 2n 個括號的所有方式)。
  2. 檢查每個組合是否有效,將有效的加入結果集。
  3. 檢查括號有效性
    • 從左到右遍歷字符串,用變量 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)),用於存儲所有可能的組合。

總結

本題是經典的括號生成問題,最常用的方法是 回溯法,它結構清晰且效率高,能夠在有限的遞歸深度內生成所有合法組合。動態規劃法則適合於理解更為結構化的解法,暴力法則可作為基礎練習。

歡迎來到我的部落格!這裡記錄了軟體工程師的日常生活點滴,並分享程式設計與演算法的實用教學。無論你是初學者還是有經驗的開發者,都能在這裡找到深入淺出的技術解析與實戰技巧。此外,我也會分享工作中的心路歷程與學習心得,讓你不僅學到技術,更能瞭解軟體開發的實際應用與挑戰。希望透過這個平台,能與你共同成長,激發對技術的熱情!
留言0
查看全部
avatar-img
發表第一個留言支持創作者!
給定兩個遞增排序的鏈表 list1 和 list2,將它們合併為一個新的 遞增排序 的鏈表,並返回這個新鏈表。新的鏈表應該由這兩個鏈表中的節點組成,而不應創建新的節點。最後回傳合併後的鍊錶的頭節點。
給定一個僅包含字元 '(', ')', '{', '}', '[' 和 ']' 的字串 s,確定輸入字串是否有效。
給定一個Linked list的head,從這個Linked list的末尾刪除第 n 個節點並返回其head。
給定一個包含 n 個整數的陣列 nums,傳回所有唯一的四元組 [nums[a], nums[b], nums[c], nums[d]] 的數組,使得該答案滿足題目的每項要求。
給定一組字符串,找出它們的最長公共前綴 (Longest Common Prefix)。如果沒有公共前綴,返回空字串 ""。
給定一個包含 2 到 9 之間數字的字串,傳回該數字可以表示的所有可能的字母組合。以任意順序回傳答案。 參考附圖為數字對字母的映射(就像電話按鈕一樣)。
給定兩個遞增排序的鏈表 list1 和 list2,將它們合併為一個新的 遞增排序 的鏈表,並返回這個新鏈表。新的鏈表應該由這兩個鏈表中的節點組成,而不應創建新的節點。最後回傳合併後的鍊錶的頭節點。
給定一個僅包含字元 '(', ')', '{', '}', '[' 和 ']' 的字串 s,確定輸入字串是否有效。
給定一個Linked list的head,從這個Linked list的末尾刪除第 n 個節點並返回其head。
給定一個包含 n 個整數的陣列 nums,傳回所有唯一的四元組 [nums[a], nums[b], nums[c], nums[d]] 的數組,使得該答案滿足題目的每項要求。
給定一組字符串,找出它們的最長公共前綴 (Longest Common Prefix)。如果沒有公共前綴,返回空字串 ""。
給定一個包含 2 到 9 之間數字的字串,傳回該數字可以表示的所有可能的字母組合。以任意順序回傳答案。 參考附圖為數字對字母的映射(就像電話按鈕一樣)。
你可能也想看
Google News 追蹤
Thumbnail
嘿,大家新年快樂~ 新年大家都在做什麼呢? 跨年夜的我趕工製作某個外包設計案,在工作告一段落時趕上倒數。 然後和兩個小孩過了一個忙亂的元旦。在深夜時刻,看到朋友傳來的解籤網站,興致勃勃熬夜體驗了一下,覺得非常好玩,或許有人玩過了,但還是想寫上來分享紀錄一下~
Thumbnail
題目敘述 Combination Sum II_Leetcode #40 給定一個整數陣列candidates 和 目標值target。 每個陣列元素只能選擇一次,請問有多少種組合方法,可以使得組合數總和 = target? 請把滿足組合數總和 = target的組合方法以陣列的形式返回答案
Thumbnail
題目敘述 Patching Array 題目給定一個整數陣列, 請問還要補上多少個數字,才能用這些數字的和拼湊出所有1~n的整數。
Thumbnail
題目敘述 Combination Sum IV 給定一個輸入陣列nums,和目標值target,從nums裡面挑數字去湊出總和 = target,數字可以重複挑選。 請問有多少排列數可以湊出target? 註: 排列數的意思就是位置不同代表兩種不同的方法數。
Thumbnail
Leetcode 精選75題 題目與題解 熱門考點 目錄 (持續更新中) 建議從左側目錄 或者 按Ctrl+F輸入關鍵字進行搜尋
Thumbnail
題目會給定一個陣列nums和一個目標值goal。計算子陣列總和=goal的數目有多少。演算法包含前綴和和字典的技巧,時間複雜度為O(n),空間複雜度為O(n)。
Thumbnail
題目敘述 題目會給定我們一個輸入陣列nums,要求我們掃描美個陣列元素nums[i],計算除了nums[i]以外的陣列元素連乘積。 題目的原文敘述 測試範例 Example 1: Input: nums = [1,2,3,4] Output: [24,12,8,6] nums[0] 以
Thumbnail
題目敘述 題目會給定一個輸入字串s和一套編碼規則,要求我們針對字串s進行解碼,並且以字串的形式返回答案。 編碼規則: 數字[字串] -> []內的字串以對應倍數做展開,而且允許巢狀編碼。 例如: 3[a] 解碼完就是 aaa 2[bc] 解碼完就是 bcbc 2[a2[b]] = 2
Thumbnail
題目敘述 題目會給定我們兩個輸入字串word1, word2,要求我們依照word1,word2,word1,word2, ... 交叉前進的方式,合併兩個字串,作為輸出。 題目的原文敘述 測試範例 Example 1: Input: word1 = "abc", word2 = "pq
Thumbnail
題目敘述 題目會給我們一個參數k 和 目標值n。 請問我們從1~9內挑k個相異的數字,使得他們的總和為n 的組合數有多少? 挑選時,每個數字必須相異,而且每個數字只能選一次。 題目的原文敘述 測試範例 Example 1: Input: k = 3, n = 7 Output: [
Thumbnail
嘿,大家新年快樂~ 新年大家都在做什麼呢? 跨年夜的我趕工製作某個外包設計案,在工作告一段落時趕上倒數。 然後和兩個小孩過了一個忙亂的元旦。在深夜時刻,看到朋友傳來的解籤網站,興致勃勃熬夜體驗了一下,覺得非常好玩,或許有人玩過了,但還是想寫上來分享紀錄一下~
Thumbnail
題目敘述 Combination Sum II_Leetcode #40 給定一個整數陣列candidates 和 目標值target。 每個陣列元素只能選擇一次,請問有多少種組合方法,可以使得組合數總和 = target? 請把滿足組合數總和 = target的組合方法以陣列的形式返回答案
Thumbnail
題目敘述 Patching Array 題目給定一個整數陣列, 請問還要補上多少個數字,才能用這些數字的和拼湊出所有1~n的整數。
Thumbnail
題目敘述 Combination Sum IV 給定一個輸入陣列nums,和目標值target,從nums裡面挑數字去湊出總和 = target,數字可以重複挑選。 請問有多少排列數可以湊出target? 註: 排列數的意思就是位置不同代表兩種不同的方法數。
Thumbnail
Leetcode 精選75題 題目與題解 熱門考點 目錄 (持續更新中) 建議從左側目錄 或者 按Ctrl+F輸入關鍵字進行搜尋
Thumbnail
題目會給定一個陣列nums和一個目標值goal。計算子陣列總和=goal的數目有多少。演算法包含前綴和和字典的技巧,時間複雜度為O(n),空間複雜度為O(n)。
Thumbnail
題目敘述 題目會給定我們一個輸入陣列nums,要求我們掃描美個陣列元素nums[i],計算除了nums[i]以外的陣列元素連乘積。 題目的原文敘述 測試範例 Example 1: Input: nums = [1,2,3,4] Output: [24,12,8,6] nums[0] 以
Thumbnail
題目敘述 題目會給定一個輸入字串s和一套編碼規則,要求我們針對字串s進行解碼,並且以字串的形式返回答案。 編碼規則: 數字[字串] -> []內的字串以對應倍數做展開,而且允許巢狀編碼。 例如: 3[a] 解碼完就是 aaa 2[bc] 解碼完就是 bcbc 2[a2[b]] = 2
Thumbnail
題目敘述 題目會給定我們兩個輸入字串word1, word2,要求我們依照word1,word2,word1,word2, ... 交叉前進的方式,合併兩個字串,作為輸出。 題目的原文敘述 測試範例 Example 1: Input: word1 = "abc", word2 = "pq
Thumbnail
題目敘述 題目會給我們一個參數k 和 目標值n。 請問我們從1~9內挑k個相異的數字,使得他們的總和為n 的組合數有多少? 挑選時,每個數字必須相異,而且每個數字只能選一次。 題目的原文敘述 測試範例 Example 1: Input: k = 3, n = 7 Output: [