🧠 Python小練習系列 Vol.3：生成有效括號組合（回溯 + DFS）

👋 本期我們來刷一道 LeetCode 熱門經典題，借此掌握回溯算法的精髓 —— 生成有效括號組合，是學習遞歸 & DFS 的黃金題型！

---

🧩 一、題目描述

給定一個整數 n，代表括號對的數量，請你生成所有格式正確的括號組合。

示例：

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

---

🧠 二、解題思路

我們可以用「回溯 + 深度優先搜索（DFS）」的方法，逐步構建每一位括號組合。

合法組合規則：

• 左括號 ( 的數量不能超過 n
• 右括號 ) 的數量不能超過左括號數量

回溯核心：

• 用遞歸函數 dfs(path, left, right)
• 當 path 滿足長度條件時，將其加入結果
• 嘗試添加 ( 或 )，并繼續向下探索

---

👨?💻 三、Python代碼實現

def generate_parentheses(n):result = []def dfs(path, left, right):if len(path) == 2 * n:result.append(path)returnif left < n:dfs(path + '(', left + 1, right)if right < left:dfs(path + ')', left, right + 1)dfs('', 0, 0)return result

---

📌 四、運行示例

print(generate_parentheses(3))
# 輸出：['((()))', '(()())', '(())()', '()(())', '()()()']

---

🧩 五、解題思維小結

步驟	說明
定義參數	當前構造字符串 path、左括號數 left、右括號數 right
剪枝策略	左右括號數量必須符合規則
終止條件	path 長度等于 2 * n 即為完整解

? 本題關鍵在于：控制遞歸分支合法性，避免冗余搜索

---

💡 六、進階思考

• 💬 輸出的括號組合可以按字典序排列嗎？
• 🧠 用棧模擬生成過程，可視化 DFS？
• ?? 如果限制時間/內存，如何提前剪枝？

---

?? 結語

回溯法很像在“決策樹”中找答案，本題正是練習遞歸與剪枝的完美例子！

📌 下一期預告：迷宮尋路：回溯走迷宮（二維矩陣）

---

👉 點贊 👍 + 收藏 🌟，練好算法，刷題不慌！