Generate Parentheses
#NeetCode150 #Medium
LeetCode.icon問題
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
example
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
解法
類題
Valid Parentheses
Valid Parenthesis String
()の全組み合わせ総数(allParens)は$ \frac{(2n)!}{(n!)^2}
これを総当たりで走査。
これらから有効な(well-formedな)組み合わせのみretに格納して返している
時間計算量・空間計算量ともに$ O(2^{2n}n)
code:main.go
var allParens []string
func generateParenthesis(n int) []string {
allParens = []string{}
recurParens("", n, n)
var ret []string
outer:
for _, parens := range allParens {
var cur int
for _, paren := range parens {
if paren == rune('(') {
cur += 1
} else {
cur -= 1
}
if cur < 0 { continue outer }
}
ret = append(ret, parens)
}
return ret
}
func recurParens(parens string, lCnt, rCnt int) {
if lCnt == 0 && rCnt == 0 {
allParens = append(allParens, parens)
}
if lCnt > 0 {
recurParens(parens + "(", lCnt-1, rCnt)
}
if rCnt > 0 {
recurParens(parens + ")", lCnt, rCnt-1)
}
}
解説を読むとバックトラック法を使えば時間計算量・空間計算量ともに$ O(\frac{4^n}{\sqrt n})で済むとのことなので解き直してみた
総当たりからチェックせずに済むので、こちらの方が実装もシンプルで良い。
code:main2.go
var ret []string
func generateParenthesis(n int) []string {
ret = []string{}
backtrack("", 0, n, n)
return ret
}
func backtrack(parens string, cnt, lCnt, rCnt int) {
if cnt < 0 || lCnt < 0 || rCnt < 0 { return }
if cnt == 0 && lCnt == 0 && rCnt == 0 { ret = append(ret, parens) }
if lCnt > 0 {
backtrack(parens + "(", cnt+1, lCnt-1, rCnt)
}
if rCnt > 0 {
backtrack(parens + ")", cnt-1, lCnt, rCnt-1)
}
}