括号生成器golang版本

括号生成器

//方法一
func generateParenthesis(n int) []string {
	ret := make([]string, 0)
	if n == 0 {
		return ret
	}
	ret = generateParenthesisDfs("", n, n, ret)
	return ret
}

func generateParenthesisDfs(s string, left, right int, ret []string) []string {
	if left == 0 && right == 0 {
		ret = append(ret, s)
		return ret
	}
	println(fmt.Sprintf("s=%s, left=%d,right=%d,ret=%+v", s, left, right, ret))
	if left > 0 {
		ret = generateParenthesisDfs(s+"(", left-1, right, ret)
	}
	if right > 0 && left < right {
		ret = generateParenthesisDfs(s+"(", left, right-1, ret)
	}
	return ret
}

// 方法二 动态规划的思路
func generateParenthesis2(n int) []string {
	dp := make([][]string, n+1)
	dp[0] = make([]string, 0)
	if n == 0 {
		return dp[0]
	}
	dp[0] = append(dp[0], "")
	for i := 1; i <= n; i++ {
		dp[i] = make([]string, 0)
		for j := 0; j < i; j++ {
			for _, s1 := range dp[j] {
				for _, s2 := range dp[i-j-1] {
					s := "(" + s1 + ")" + s2
					dp[i] = append(dp[i], s)
				}
			}
		}
	}
	return dp[n]
}