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 }
执行结果如下: