package main

func generateParenthesisIter(last string, left, right, goal int, res *[]string) {
	if right == goal {
		*res = append(*res, last)
		return
	}
	if left < goal {
		generateParenthesisIter(last+"(", left+1, right, goal, res)
	}
	if right < left {
		generateParenthesisIter(last+")", left, right+1, goal, res)
	}
}

func generateParenthesis(n int) []string {
	res := &[]string{}
	generateParenthesisIter("", 0, 0, n, res)
	return *res
}

/* func main() {
	fmt.Println(generateParenthesis(3))
} */