?2021-09-19：数字 n 代表生成括号的对数，请你设计一

原创

福大大架构师每日一题

修改于 2021-09-22 10:54:50

2460

修改于 2021-09-22 10:54:50

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

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

福大大答案2021-09-19：

递归。

参数1：左括号-右括号的数量。

参数2：左括号剩多少。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
    n := 3
    ret := generateParenthesis(n)
    fmt.Println(ret)
    ret2 := generateParenthesis2(n)
    fmt.Println(ret2)
}

func generateParenthesis(n int) []string {
    path := make([]byte, n<<1)
    ans := make([]string, 0)
    process(path, 0, 0, n, &ans)
    return ans
}

// path 做的决定  path[0....index-1]做完决定的！
// path[index.....] 还没做决定，当前轮到index位置做决定！

func process(path []byte, index int, leftMinusRight int, leftRest int, ans *[]string) {
    if index == len(path) {
        *ans = append(*ans, string(path))
    } else {
        // index (   )
        if leftRest > 0 {
            path[index] = '('
            process(path, index+1, leftMinusRight+1, leftRest-1, ans)
        }
        if leftMinusRight > 0 {
            path[index] = ')'
            process(path, index+1, leftMinusRight-1, leftRest, ans)
        }
    }
}

// 不剪枝的做法
func generateParenthesis2(n int) []string {
    path := make([]byte, n<<1)
    ans := make([]string, 0)
    process2(path, 0, &ans)
    return ans
}

func process2(path []byte, index int, ans *[]string) {
    if index == len(path) {
        if isValid(path) {
            *ans = append(*ans, string(path))
        }
    } else {
        path[index] = '('
        process2(path, index+1, ans)
        path[index] = ')'
        process2(path, index+1, ans)
    }
}

func isValid(path []byte) bool {
    count := 0
    for _, cha := range path {
        if cha == '(' {
            count++
        } else {
            count--
        }
        if count < 0 {
            return false
        }
    }
    return count == 0
}

执行结果如下：