Source: InterviewBit – Generate all Parentheses II

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses of length 2*n.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

Make sure the returned list of strings are sorted.

解題：

這題其實也不算太難，主要要在遞迴的狀態下想清楚要先回傳怎樣的結果，才不用完成遞迴後還要重新執行一次排序。筆者的遞迴確認程序列示如下：

首先，設定左括號跟右括號之計數，預設為 0；遞迴時欲同步更新之字串值，預設為空值""
接著是遞迴如何進行及如何跳出之遞迴設定
1. 如右括號計數跟輸入值相同，代表已完成該括號組合，將其加入輸出值並結束遞迴；
2. 如未符合條件1，如左括號計數與右括號計數相同，代表下個值必定要是左括號，
　 否則會出現無效之括號組合，故將字串值加上"("，左括號計數+1並進行遞迴更新；
3. 如未符合條件1及2，且左括號計數尚小於輸入值的情況下，可以有兩種情況：
　3.1 左括號計數+1及字串加"("並進行遞迴更新；或
　3.2 右括號計數+1及字串加")"並進行遞迴更新
　 此處須注意，依據題目要求，左括號計數增加之順位應優於執行右括號計數增加，
　 故 3.1 必須排在 3.2 之前；
4. 如條件1, 2, 3均不符合，表示只能進行右括號計數值之更新，故執行
　 字串值加上")"，右括號計數+1並進行遞迴更新之步驟。

Code:

class Solution:
	# @param A : integer
	# @return a list of strings
	def generateParenthesis(self, A):
	    ptsComb = []
	    if A == 0: return ptsComb
	    leftPts, rightPts = 0, 0
	    
	    def recursive(leftPts, rightPts, A, curr):
	        if rightPts == A:
                ptsComb.append(curr)
	        elif leftPts == rightPts:
	            recursive(leftPts+1, rightPts, A, curr + "(")
	        elif leftPts < A:
	            recursive(leftPts+1, rightPts, A, curr + "(")
	            recursive(leftPts, rightPts + 1, A, curr+")")
	        elif rightPts < A:
	            recursive(leftPts, rightPts+1, A, curr + ")")
	    
	    recursive(leftPts, rightPts, A, "")
	    return ptsComb

GitHub: GitHub

發表留言