package generateparentheses

// 22. 括号生成
// https://leetcode-cn.com/problems/generate-parentheses/

func generateParenthesis(n int) []string {
	if n == 0 {
		return nil
	}
	res := []string{}
	dfs(n, n, "", &res)
	return res
}

func dfs(li, ri int, str string, res *[]string) {
	if li == 0 && ri == 0 {
		*res = append(*res, str)
		return
	}
	if li > 0 {
		dfs(li-1, ri, str+"(", res)
	}
	if ri > 0 && li < ri {
		dfs(li, ri-1, str+")", res)
	}
}