# 【Leetcode】：22. Generate Parentheses 问题 in Go语言

u013564276 · · 1270 次点击 · · 开始浏览

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:

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

```func generateParenthesis(n int) []string {
str := make([]string,0)
position := make([]int, n * 2) //第i个小标表示位置i上是左括号还是右括号，0表示左括号1表示右括号
placeParentheses(position, &str, 0, n)
return str
}

func placeParentheses(position []int, str *[]string, i, n int) {
if i == 2 * n { //当所有的括号都放完了
var s string
for _, v := range position {
if v == 0 {
s += "("
} else {
s += ")"
}
}
*str = append(*str, s)
return
}
if isValid(position, i, 0, n) { //放左括号是否合法
position[i] = 0
placeParentheses(position, str, i + 1, n)
}
if isValid(position, i, 1, n) { //放右括号是否合法
position[i] = 1
placeParentheses(position, str, i + 1, n)
}
}

func isValid(position []int, cur int, LR int, n int) bool {
var num_left, num_right int
for i := 0; i < cur; i++ {
if position[i] == 0 {
num_left++
} else {
num_right++
}
}
if LR == 0 { //如果当前放入的是左括号
if num_left >= n {
return false
}
} else {   //如果当前放入的是右括号
if num_left <= num_right {
return false
}
}
return true
}```

0 回复

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、``单行代码``
• 支持 @ 本站用户；支持表情（输入 : 提示），见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传

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:

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

```func generateParenthesis(n int) []string {
str := make([]string,0)
position := make([]int, n * 2) //第i个小标表示位置i上是左括号还是右括号，0表示左括号1表示右括号
placeParentheses(position, &str, 0, n)
return str
}

func placeParentheses(position []int, str *[]string, i, n int) {
if i == 2 * n { //当所有的括号都放完了
var s string
for _, v := range position {
if v == 0 {
s += "("
} else {
s += ")"
}
}
*str = append(*str, s)
return
}
if isValid(position, i, 0, n) { //放左括号是否合法
position[i] = 0
placeParentheses(position, str, i + 1, n)
}
if isValid(position, i, 1, n) { //放右括号是否合法
position[i] = 1
placeParentheses(position, str, i + 1, n)
}
}

func isValid(position []int, cur int, LR int, n int) bool {
var num_left, num_right int
for i := 0; i < cur; i++ {
if position[i] == 0 {
num_left++
} else {
num_right++
}
}
if LR == 0 { //如果当前放入的是左括号
if num_left >= n {
return false
}
} else {   //如果当前放入的是右括号
if num_left <= num_right {
return false
}
}
return true
}```