括号生成

[yankewei]

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

示例 1：

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

示例 2：

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

提示：

• 1 <= n <= 8

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[yankewei]

递归

简单点说就是把所有的可能都列出来

func generateParenthesis(n int) []string {
    return generate(n,"(", [2]int{1,0}, &[]string{})
}

func generate(n int, cur string, used [2]int, set *[]string) []string {
    if used[0] > n || used[1] > n { // 已经把(用掉了n或者把)用掉了n, 那肯定不是一个有效的括号组合
	return *set
    }
    if len(cur) == n * 2 { // 括号已经用完
	if invalid(cur) {
	    *set = append(*set, cur)
	    seen[cur] = struct{}{}
	}
    } else {
	generate(n, cur + "(", [2]int{used[0]+1, used[1]}, set, seen)
	generate(n, cur + ")", [2]int{used[0], used[1]+1}, set, seen)
    }
    return *set
}

func invalid(str string) bool {
    var stack []int32
    for _, v := range str {
	if len(stack) == 0 {
	    stack = append(stack, v)
	    continue
	}
	if v == ')' && stack[len(stack)-1] == '('{
	    stack = stack[:len(stack)-1]
	} else {
	    stack = append(stack, v)
	}
    }
    return len(stack) == 0
}

回溯

再上边暴力递归的情况下，有一些数据没有必要再进入下一层循环。

func generateParenthesis(n int) []string {
    return generate(n,"(", [2]int{1,0}, &[]string{})
}

func generate(n int, cur string, used [2]int, set *[]string) []string {
    if used[0] > n || used[1] > n { // 已经把(用掉了n或者把)用掉了n, 那肯定不是一个有效的括号组合
	return *set
    }
    if len(cur) == n * 2 { // 括号已经用完
	if invalid(cur) {
	    *set = append(*set, cur)
	}
    } else {
        // 如果左括号还没用完，那就用一个
        if used[0] < n {
    	    generate(n, cur + "(", [2]int{used[0]+1, used[1]}, set)
        }
        // 要用右括号的前提是左括号比右括号用的多，否则使用右括号显然不是一个有效的括号
        if used[0] > used[1] {
            generate(n, cur + ")", [2]int{used[0], used[1]+1}, set)
        }
    }
    return *set
}

func invalid(str string) bool {
    var stack []int32
    for _, v := range str {
	if len(stack) == 0 {
	    stack = append(stack, v)
	    continue
	}
	if v == ')' && stack[len(stack)-1] == '('{
	    stack = stack[:len(stack)-1]
	} else {
	    stack = append(stack, v)
	}
    }
    return len(stack) == 0
}