22.M 括号生成

Problem: 22. 括号生成

思路

思路1：穷举法

穷举所有的可能性，然后当path的长度达到2 * n时，判断结果是否有效，有效则加入结果集。

思路2：回溯法

思路1存在较多的无效path，因此可以用回溯法进行优化，仅在当前path依然有效的情况下才添加(或)。

• 当open < n时，可以继续添加(

• 当close < open时，可以继续添加)

Code

代码1：

func generateParenthesis(n int) []string {
	var path string
	var ans []string
	generate(n, 0, path, &ans)
	return ans
}

func generate(n int, start int, path string, ans *[]string) {
	if start == 2*n {
		if valid(path) {
			*ans = append(*ans, path)
		}
		return
	}

	path += "("
	generate(n, start+1, path, ans)
	path = path[0 : len(path)-1]
	path += ")"
	generate(n, start+1, path, ans)
}

func valid(path string) bool {
	val := 0
	for _, ch := range path {
		if ch == '(' {
			val++
		} else {
			val--
		}

		if val < 0 {
			return false
		}
	}

	return val == 0
}

代码2：

func generateParenthesis(n int) []string {
	var path string
	var ans []string
	backtrace(n, 0, 0, path, &ans)
	return ans
}

func backtrace(n int, open int, close int, path string, ans *[]string) {
	if len(path) == 2*n {
		*ans = append(*ans, path)
		return
	}

	if open < n {
		path += "("
		backtrace(n, open+1, close, path, ans)
		path = path[0 : len(path)-1]
	}

	if close < open {
		path += ")"
		backtrace(n, open, close+1, path, ans)
		path = path[0 : len(path)-1]
	}
}