問題描述
數字n代表生成括号的對數，請設計一個函數，用于能夠生成所有可能的并且有效的括号組合。
示例：
輸入：n = 3
輸出：[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
解決方案
這道題的第一思路是用全排列把所有的括号可能排出來，再用棧的思路來檢測是否為有效括号組。然後去百度了下全排列的算法代碼，要用到回溯，而且代碼很長。既然全排要用回溯，還不如直接用回溯算了。然後就發現，這個括号很像二叉樹。
圖2.1思路分析二叉樹示意
簡單的畫了下。衆所周知樹和回溯可是老夥伴了。代碼實作的主要突破是括号的插入方法和向下搜尋的條件。借用棧的思路可以知道插入‘）’時必須有‘（’而且‘（’的數量必須比‘）’的數量多有了這一點就可以開始代碼了。
python代碼：
| class Solution: def generateParenthesis(self, n): res = [] self.dfs(res, n, n, '') return res def dfs(self, res, left, right, path): #周遊深度達到n及左右括号都用完了時傳回path路徑 if left==right==0: res.append(path) return #插入右括号的時機 if left<right: self.dfs(res,left,right-1,path+')') #插入左括号的時機 if left>0: self.dfs(res,left-1,right,path+'(') x=Solution() print(x.generateParenthesis(n=3)) |
|---|
結語
回溯法主要可以用在三種問題上（前題是需要窮舉）：
1 .判斷有沒有解
2.求所有解的數量或具體資訊
3.求最優解
這道題就屬于第二種。
回溯法的基本套路是使用兩個變量： res 和 path，res 表示最終的結果，path 儲存已經走過的路徑。如果搜到一個狀态滿足題目要求，就把 path 放到 res 中。