22. 括号生成(dfs)

22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

提示：

• 1 <= n <= 8

func generateParenthesis(n int) []string {
    var res = make([]string, 0)
    if n <= 0 {
        return res 
    }
    var dfs func(string,int,int)
    dfs = func(path string, open int, close int) {
　　　　　// 遍历完成，将结果记录在res中
        if len(path) == 2*n {
            res = append(res,path)
            return
        }
　　　　　// 左（开）括号数量过半不再向下搜索
        if open < n {
            dfs(path + "(", open + 1, close)
        }
　　　　　// 右（闭）括号数量比开括号多则为无效组合
        if close < open {
            dfs(path + ")", open, close + 1)
        }
    }
    dfs("",0,0)
    return res
}