package main

import "fmt"

// 22. 括号生成
func generateParenthesis(n int) []string {
	var ans []string
	parentNums := []int{n, n}    // 开局左右括号分别有n个
	dfs(n, "", parentNums, &ans) // 传切片指针才行，直接穿ans，没有用，或者把dfs写成闭包
	return ans
}
func dfs(n int, path string, parentNums []int, ans *[]string) {
	if len(path) == 2*n {
		*ans = append(*ans, path) // 字符串可以直接append，不用深拷贝
		return
	}

	// 做选择。只有左右括号两种选择
	if parentNums[0] > 0 { // 只要还有左括号，就可以选择
		path += "("
		parentNums[0]--
		dfs(n, path, parentNums, ans)
		path = path[:len(path)-1]
		parentNums[0]++
	}

	if parentNums[1] > 0 && parentNums[1] > parentNums[0] {
		// 右括号还有，而且左括号剩的个数比左括号多，才可以选右括号，如果比左括号少，这种场景在前面的过程中已经排除掉了
		path += ")"
		parentNums[1]--
		dfs(n, path, parentNums, ans)
		path = path[:len(path)-1]
		parentNums[1]++
	}
}

// 分别记录左括号个数，右括号个数

func main22() {
	fmt.Println(generateParenthesis(3))
}