/*
 * @lc app=leetcode.cn id=22 lang=golang
 *
 * [22] 括号生成
 */

// @lc code=start
func generateParenthesis(n int) (res []string) {
	var str string
	var generate func(left, right int)
	generate = func(left, right int) {
		if len(str) == 2*n {
			res = append(res, str)
			return
		}

		if left < n {
			str = str + "("
			generate(left+1, right)
			str = str[:len(str)-1]
		}
		if right < left {
			str = str + ")"
			generate(left, right+1)
			str = str[:len(str)-1]
		}
	}

	generate(0, 0)
	return
}

// @lc code=end