package Backtrack
func generateParenthesis(n int) []string {
result := make([]string, 0)
var path string
var f func(index, leftP, rightP int)
f = func(index, leftP, rightP int) {
if index == 2*n {
result = append(result, path)
return
}
// (1) 左括号数量小于 N 时, 可以放左括号
if leftP < n {
path = path + string('(')
f(index+1, leftP+1, rightP)
path = path[:len(path)-1]
}
// (2) 右括号数量小于左括号时, 可以放右括号
if rightP < leftP {
path = path + string(')')
f(index+1, leftP, rightP+1)
path = path[:len(path)-1]
}
}
f(0, 0, 0)
return result
}