LeetCode 熱題 100 | 22. 括號生成

大家好，今天我們來解決一道經典的算法題——括號生成。這道題在 LeetCode 上被標記為中等難度，要求生成所有可能的并且有效的括號組合。這是一道非常經典的回溯法題目，非常適合用來練習遞歸和回溯的技巧。下面我將詳細講解解題思路，并附上 Python 代碼實現。

---

問題描述

數字 n 代表生成括號的對數，請你設計一個函數，用于能夠生成所有可能的并且有效的括號組合。

示例 1：

輸入：n = 3
輸出：["((()))", "(()())", "(())()", "()(())", "()()()"]

示例 2：

輸入：n = 1
輸出：["()"]

提示：

• 1 <= n <= 8

---

解題思路

核心思想

1. 回溯法：

   • 回溯法是一種通過遞歸枚舉所有可能解的方法。
   • 在生成括號組合的過程中，我們需要確保每個生成的括號組合都是有效的。

2. 有效括號的條件：

   • 在生成過程中，左括號的數量不能超過 n。
   • 在生成過程中，右括號的數量不能超過左括號的數量。
   • 當左括號和右括號的數量都達到 n 時，生成的括號組合是有效的。

3. 遞歸終止條件：

   • 當左括號和右括號的數量都達到 n 時，將當前生成的括號組合加入結果列表。

4. 遞歸過程：

   • 如果左括號的數量小于 n，可以添加一個左括號。
   • 如果右括號的數量小于左括號的數量，可以添加一個右括號。
   • 在遞歸返回時，移除最后一個括號（回溯）。

---

Python代碼實現

class Solution:def generateParenthesis(self, n):""":type n: int:rtype: List[str]"""result = []def backtracking(left, right, path):# 遞歸終止條件if left == n and right == n:result.append(path)return# 添加左括號if left < n:backtracking(left + 1, right, path + "(")# 添加右括號if right < left:backtracking(left, right + 1, path + ")")backtracking(0, 0, "")return result

---

代碼解析

1. 回溯函數 backtracking：

   • 參數：
     • left：當前左括號的數量。
     • right：當前右括號的數量。
     • path：當前生成的括號組合。
   • 遞歸終止條件：當左括號和右括號的數量都達到 n 時，將當前生成的括號組合加入結果列表 result。
   • 添加左括號：如果左括號的數量小于 n，可以添加一個左括號。
   • 添加右括號：如果右括號的數量小于左括號的數量，可以添加一個右括號。

2. 結果列表 result：

   • 用于存儲所有生成的有效括號組合。

3. 路徑字符串 path：

   • 用于存儲當前遞歸過程中正在構建的括號組合。

---

復雜度分析

• 時間復雜度：O(2^(2n) / sqrt(n))，生成所有可能的括號組合的數量是卡特蘭數。
• 空間復雜度：O(n)，遞歸調用棧的深度為 n，同時需要存儲當前路徑 path。

---

示例運行

示例 1

輸入：n = 3
輸出：["((()))", "(()())", "(())()", "()(())", "()()()"]

示例 2

輸入：n = 1
輸出：["()"]

---

總結

通過回溯法，我們可以高效地生成所有可能的并且有效的括號組合。這種方法利用遞歸枚舉所有可能的括號組合，并通過回溯避免無效的組合。希望這篇題解對大家有所幫助，如果有任何問題，歡迎在評論區留言討論！

關注我，獲取更多算法題解和編程技巧！