递归和回溯解决括号匹配问题

递归和回溯解决括号匹配问题

递归在之前的文章中有提及，有朋友在后台大呼不过瘾，刚好又刷到了一道可以用到递归的算法题，还是我们的老朋友：匹配有效括号，废话不多说，先上题目。

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。   示例： 输入：n = 3 输出：[ "((()))", "(()())", "(())()", "()(())", "()()()" ] 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/generate-parentheses

经过分析，这涉及到了两个关键问题：

如何判断组合成的括号字符串是有效的

如何构建所有可能性的括号字符串。

第一个问题比较容易想通，必须要左右括号成对出现即可。
如果是暴力解法可以考虑把这两个问题分成两步去处理好，而如果是用递归，肯定是希望每次递归的时候不仅创建出排列组合，且这个组合出来的字符串是有效的。

func generateParenthesis(n int) []string { return generate(n) } func generate(n int) []string { cache := map[int][]string{} if cache[n] != nil { return cache[n] } var ans []string if n == 0 { ans = append(ans, "") } else { for c := 0; c < n; c++ { currentLeft := generate(c) currentRight := generate(n - c -1) for _, value_left := range currentLeft { for _, value_right := range currentRight { ans = append(ans, "(" + value_left + ")" + value_right) } } } } cache[n] = ans return ans }

递归的关键在于找到边界，也就是分别对左括号和右括号的创建进行递归，这样就能生成出符合条件的字符串。总体来说这次递归的解法非常符合人性，条理清晰，也用到一个cache的map来存储结果，提高执行效率。

其实这道题也可以使用回溯的方法来实现，具体代码实现如下：

func generateParenthesis2(n int) []string { ans := new([]string) // 设置一个指向类型为string的切片的指针 var curr []byte backtrack(ans, curr, 0, 0, n) return *ans // 反取指针，获得结果切片 } // 回溯函数 func backtrack(ans *[]string, curr []byte, open int, close int, max int) { if len(curr) == max * 2 { *ans = append(*ans, string(curr[:])) return } if open < max { // 左括号没有超过最大值，则添加做括号，最后删除切片的最后一个元素 curr = append(curr, '(') backtrack(ans, curr, open+1, close, max) curr = append(curr[0:len(curr)-1], curr[len(curr):]...) // 这个删除方式最直接，但是 } if close < open { // 当右括号比作括号少，则添加，最后删除切片的最后一个元素 curr = append(curr, ')') backtrack(ans, curr, open, close+1, max) curr = append(curr[0:len(curr)-1], curr[len(curr):]...) } }

回溯也就是动态规划，把每次结果都带入到下一次回溯中，通过比较开闭括号的个数，来动态地调整。
算法题有时候可以考虑多种解法去实现，刷题的同时也能体会到不同编程语言的妙处。
本文首发自我的微信公众号：成都有娃儿，欢迎关注。