刷题记录 HOT100回溯算法-5：22. 括号生成

题目：22. 括号生成

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

示例 1：

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

示例 2：

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

提示：

• 1 <= n <= 8

一、模式识别

1.回溯法

括号组合：组合问题，

访问规则：组括号，需要根据括号规则对括号计数

2.括号规则

即每有一个"("，便有一个")"与之对应，且每对括号中"("先于")"

回溯过程中，path中的")"的数量小于等于"("，

第一个符号必须是“(”

二.代码实现

参照组合总和的思路，用n和m分别对剩余的"("和")"计数，

每节点层内根据计数n和m决定探索方向，

n每减一，m便加一，体现组括号规则

数组写法：

class Solution:def backtracking(self, n, m, path, ans):if n == 0 and m == 0:ans.append(''.join(path))returnif n > 0:n -= 1m += 1path.append('(')self.backtracking(n, m, path, ans)n += 1m -= 1path.pop()if m > 0:m -= 1path.append(')')self.backtracking(n, m, path, ans)m += 1path.pop()def generateParenthesis(self, n: int) -> List[str]:ans = []self.backtracking(n, 0, [], ans)return ans

python：3ms 

字符串写法：

class Solution:def backtracking(self, n, m, path, ans):if n == 0 and m == 0:ans.append(path)returnif n > 0:n -= 1m += 1path += '('self.backtracking(n, m, path, ans)n += 1m -= 1path = path[: -1]if m > 0:m -= 1path += ')'self.backtracking(n, m, path, ans)m += 1path = path[: -1]def generateParenthesis(self, n: int) -> List[str]:ans = []self.backtracking(n, 0, "", ans)return ans

python：0ms