22. 括号生成（中等）

• 难度: 中等
• 考察: https://leetcode-cn.com/problems/generate-parentheses/
• 来源: https://github.com/azl397985856/leetcode/blob/master/problems/22.GenerateParentheses.md
• 题解: https://leetcode-cn.com/problems/generate-parentheses/solution/gua-hao-sheng-cheng-by-leetcode-solution/

题目

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

示例:

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

思路

暴力递归

生成所有可能性，判断正确性，并去重后返回

回溯递归

深度优先搜索(回溯思想)，从空字符串开始构造，做加法。

关键点

• 当 l < r 时记得剪枝

复杂度

• 时间复杂度：O(2^N)
• 空间复杂度：O(2^N)

代码

暴力递归

func generateParenthesis(n int) []string {
	if n == 0 {
		return []string{}
	}
	rr := make([]rune, n*2)
	mm := make(map[string]struct{})
	generate(rr, 0, mm)
	var result []string
	for m := range mm {
		result = append(result, m)
	}
	return result
}

func generate(rr []rune, pos int, mm map[string]struct{}) {
	if pos+1 > len(rr) {
		if valid(rr) {
			mm[string(rr)] = struct{}{}
		}
		return
	}
	rr[pos] = '('
	generate(rr, pos+1, mm)
	rr[pos] = ')'
	generate(rr, pos+1, mm)
}

func valid(rr []rune) bool {
	var balance int
	for _, r := range rr {
		if r == '(' {
			balance++
		} else {
			balance--
		}
		if balance < 0 {
			return false
		}
	}
	return balance == 0
}

回溯递归

func generateParenthesis(n int) []string {
	if n == 0 {
		return []string{}
	}
	rr := make([]rune, n*2)
    result = make([]string,0)
	generate(rr, n, n, n*2)
	return result
}

var result []string

func generate(rr []rune, left, right, length int) {
	if left == right && left == 0 {
		result = append(result, string(rr))
		return
	}
	if left > 0 {
		rr[length-left-right] = '('
		generate(rr, left-1, right, length)
	}
	if right > left {
		rr[length-left-right] = ')'
		generate(rr, left, right-1, length)
	}
}