題目:
數字n代表生成括號的對數,設計一個函數,用于生成所有可能并且有效的括號組合。
方法一:回溯
可以生成所有?2**2n?個?‘(’?和?‘)’?字符構成的序列,然后檢查每一個是否有效即可
為了生成所有序列,我們可以使用遞歸。長度為?n?的序列就是在長度為?n?1?的序列前加一個?‘(’?或?‘)’。
為了檢查序列是否有效,遍歷這個序列,并使用一個變量 balance 表示左括號的數量減去右括號的數量。如果在遍歷過程中 balance 的值小于零,或者結束時 balance 的值不為零,那么該序列就是無效的,否則它是有效的。
可以只在序列仍然保持有效時才添加?‘(’?或?‘)’,通過跟蹤到目前為止放置的左括號和右括號的數目來做到這一點,如果左括號數量不大于?n,我們可以放一個左括號。如果右括號數量小于左括號的數量,我們可以放一個右括號。
class Solution(object):def generateParenthesis(self, n):""":type n: int:rtype: List[str]"""ans=[] #列表,用于存儲所有有效的括號組合def backtrack(S,left,right): #遞歸回溯函數,當前構造的括號序列,當前左括號的數目,當前右括號的數目if len(S)==2*n: #長度達到合法括號的序列ans.append(''.join(S))#列表 S 變成字符串,加入列表中returnif left<n: #當左括號數目不達標時S.append("(")backtrack(S,left+1,right) #加入左括號后繼續構造S.pop()#遞歸返回后,將最后添加的 ( 移除,恢復原狀(回溯)if right<left: #只有 right < left 時,才能添加 ),確保括號序列合法S.append(")") #加了一個 ) 之后繼續嘗試構造backtrack(S,left,right+1)S.pop() # 將最后添加的 ) 移除,恢復原狀backtrack([],0,0)return ans
時間復雜度:O(?4*n/n**1/2?),在回溯過程中,每個答案需要?O(n)?的時間復制到答案數組中
空間復雜度:O(n)
方法二:按括號序列的長度遞歸
任何一個括號序列都一定是由?‘(’?開頭,并且第一個?‘(’?一定有一個唯一與之對應的?‘)’,每一個括號序列可以用?(a)b?來表示,其中?a?與?b?分別是一個合法的括號序列(可以為空)。
生成所有長度為?2n?的括號序列,我們定義一個函數?generate(n)?來返回所有可能的括號序列。那么在函數?generate(n)?的過程中:
需要枚舉與第一個?‘(’?對應的?‘)’?的位置?2i+1
遞歸調用?generate(i)?即可計算?a?的所有可能性
遞歸調用?generate(n?i?1)?即可計算?b?的所有可能性
遍歷?a?與?b?的所有可能性并拼接,即可得到所有長度為?2n?的括號序列
為了節省計算時間,在每次?generate(i)?函數返回之前,把返回值存儲起來,下次再調
用?generate(i)?時可以直接返回,不需要再遞歸計算
class Solution(object):def generateParenthesis(self, n):""":type n: int:rtype: List[str]"""if n==0: #沒有括號對return [""]ans=[]for c in range(n): #讓c在0到n-1之間遍歷,表示把 n 對括號分成兩部分,左部分:c 對括號;右部分n - 1 - c 對括號for left in self.generateParenthesis(c):#遞歸調用自己,求出 c 對括號的所有可能組合,并把結果賦值給 left,相當于生成左部分括號的所有可能情況for right in self.generateParenthesis(n - 1 - c):#生成右部分括號的所有可能情況ans.append('({}){}'.format(left,right)) #負責把 left 和 right 組合return ans
時間復雜度:O(?4*n/n**1/2?)
空間復雜度:O(?4*n/n**1/2?)此方法除答案數組外,中間過程中會存儲與答案數組同樣數量級的臨時數組,是所需要的空間復雜度。
源自力扣官方題解