括号生成

题目描述：

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

示例 1：

输入：n = 3
输出：[“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]
示例 2：

输入：n = 1
输出：[“()”]

提示：

1 <= n <= 8
通过次数408,548提交次数528,598

思路:

用dfs回溯法遍历所有可能

代码:

func generateParenthesis(n int) []string {
    var res []string
    var s string
    var dfs func(l,r int,s string)
    dfs = func(l,r int,s string){
        if l ==n && r == n{
            res = append(res,s)
            return
        }else if l>n || r >n || r>l{
            return
        }
        s = s+"("
        dfs(l+1,r,s)
        s = s[:len(s)-1]
        s = s+")"
        dfs(l,r+1,s)
        s = s[:len(s)-1]
    }
    dfs(0,0,s)
    return res
}

代码效率：

执行用时：4 ms, 在所有 Go 提交中击败了10.59%的用户
内存消耗：2.8 MB, 在所有 Go 提交中击败了52.39%的用户