括号生成

1. 题目描述

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

2. 思路

1. 思路一
   • 全排列+栈
   • 对于每个位置，既可以用(，也可以用)
   • 穷举完毕后验证是否合法括号（栈）
2. 思路二
   1. 
   2. 对左右括号剪枝

3. 实现

3.1. 全排列+栈

func generateParenthesis(n int) []string {
    res := make([]string, 0)

    path := make([]rune, n*2)
    generateParenthesisDFS(n*2, 0, path, &res)

    return res
}

func generateParenthesisDFS(n int, index int, path []rune, res *[]string) {
    if index == n {
        if isValid(path) {
            *res = append(*res, string(path))
        }
        return
    }

    path[index] = '('
    generateParenthesisDFS(n, index+1, path, res)
    path[index] = ')'
    generateParenthesisDFS(n, index+1, path, res)
    
}

func isValid(runes []rune) bool {
    stack := make([]rune, 0)

    for _, r := range runes {
        if isLeft(r) {
            stack = append(stack, r)
        }else if isRight(r) {
            if len(stack) == 0 {
                return false
            }
            stack = stack[:len(stack)-1]
        }
    }

    return len(stack) == 0
}

func isLeft(ch rune) bool {
    return ch == '('
}

func isRight(ch rune) bool {
    return ch == ')'
}

3.2. 对左右括号剪枝

var m = map[rune]rune {
    '(':')',
}


func generateParenthesis(n int) []string {
    res := make([]string, 0)
    path := make([]rune, 2*n)
    dfs(n, n, 0, path, &res)
    return res
}

func dfs(left int, right int, index int, path []rune, res *[]string) {
    if left == 0 && right == 0 {
        str := string(path)
        if isValid(str) {
            *res = append(*res, str)
        }
        return
    }
    
    //left > right 是非法前缀，直接剪枝
    if (left > right) {
        return
    }

    if left > 0 {
        path[index] = '('
        dfs(left-1, right, index+1, path, res)
    }
    if right > 0 {
        path[index] = ')'
        dfs(left, right-1, index+1, path, res)
    }

}


func isValid(s string) bool {
    stack := make([]rune, 0)
    for _, r := range []rune(s) {
        if isLeft(r) {
            stack = append(stack, r)
        } else if isRight(r){
            if len(stack) > 0 && isMatch(stack[len(stack)-1], r) {
                stack = stack[:len(stack)-1]
                continue
            }
            return false
        } else {
            return false
        }
    }

    return len(stack) == 0
}

func isLeft(r rune) bool {
    return r == '(' 
}

func isRight(r rune) bool {
    return r == ')'
}

func isMatch(left, right rune) bool{
    return m[left] == right
}

4. 参考

• 回溯算法（深度优先遍历）+ 广度优先遍历（Java） - 括号生成 - 力扣（LeetCode）