未分類

Generate Parentheses

Backtracking, Go, LeetCode, String

Generate Parentheses

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

For example:

Given n = 3, a solution set is:

1
2
3
4
5
6
7
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]
提示 解題應用
Backtracking Recursive
String 規律觀查

Default:

1
2
3
func generateParenthesis(n int) []string {
}

解答思路:

原本直覺是想到要用stack做，不過如果是檢查或是產生另一半對應的話才需要使用，這邊是重頭到尾都是自己產生，所以就可以由判斷來產生合理的結果，藉由遞回的方式來找出所有可能，並且透過計算開口”(“剩餘尚未對應的次數來除去不合理的結果，就可以找到所有正確的組合。

程式碼解說:

因為是用遞回來做，所以一開始便代入初始值來開始遞回，透過觀查可以發現不管哪個結果開頭一定都是”(“，至於參數第一個為尚可新增的字串長度，再來則是開口”(“剩餘尚未對應的次數及目前的字串結果

1
2
3
func generateParenthesis(n int) []string {
	return parenthesis(n*2-1, 1, "(")
}

如果可新增的字串長度為0的話，此時就直接將字串包入陣列中做回傳，如果能新增的長度洽好等於開口”(“剩餘尚未對應的次數，表示接下來就一定只能放”)”在後頭，所以就直接用一迴圈將剩餘的”)”補上並直接回傳字串陣列，或者當開口”(“剩餘尚未對應的次數為0時，此時便暫時無法將”)”接在後頭，便只遞回”(“接在結果後頭的情況，而如果不是上述任一情況便各別將”(“與”)”放入結果後頭並做遞回，最後再將兩個得到的字列陣列做合併再往上做回傳

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func parenthesis(n int, open int, str string) []string {
	if n == 0 {
		return []string{str}
	} else if n == open {
		for i := 1; i <= n; i++ {
			str += ")"
		}
		return []string{str}
	} else if open == 0 {
		return parenthesis(n-1, open+1, str+"(")
	}
	addOpen := parenthesis(n-1, open+1, str+"(")
	addClose := parenthesis(n-1, open-1, str+")")
	return append(addOpen, addClose...)
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func generateParenthesis(n int) []string {
	return parenthesis(n*2-1, 1, "(")
}
func parenthesis(n int, open int, str string) []string {
	if n == 0 {
		return []string{str}
	} else if n == open {
		for i := 1; i <= n; i++ {
			str += ")"
		}
		return []string{str}
	} else if open == 0 {
		return parenthesis(n-1, open+1, str+"(")
	}
	addOpen := parenthesis(n-1, open+1, str+"(")
	addClose := parenthesis(n-1, open-1, str+")")
	return append(addOpen, addClose...)
}

總結:

括弧”(“與”)”代表1組，給予一數字n，列出n組所有可能的括弧組合，只要藉由遞回的方式來找出所有可能，並且透過計算開口”(“剩餘尚未對應的次數來除去不合理的結果，就可以找到所有正確的組合。

分享到