LeetCode/exercises/dynamic-programming/22-generate-parenthesis/golang/main.go

54 lines
990 B
Go

package main
import (
"strings"
"container/list"
)
/*
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example 1:
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Example 2:
()()(); (())(); ((()));
()(());
(()())
Input: n = 1
Output: ["()"]
()(); (())
Constraints:
1 <= n <= 8
*/
func rec(input []string, left int, right int, n int, ans *[]string) {
if len(input) == 2*n {
*ans = append(*ans, strings.Join(input, ""))
return
}
if left < n {
input = append(input, "(")
rec(input, left+1, right, n, ans)
input = input[0:len(input)-1]
}
if right < left {
input = append(input, ")")
rec(input, left, right+1, n, ans)
input = input[0:len(input)-1]
}
}
func generateParenthesis(n int) []string {
var output = make([]string, 2*n)
var input = make([]string, 2*n)
rec(input, 0, 0, n, &output)
return output
}
func main() {
generateParenthesis(3)
}