python|LeetCode 括号生成回溯法|leetcode

括号生成 【python|LeetCode 括号生成】题目来源：https://leetcode-cn.com/problems/generate-parentheses/submissions/
题目
给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
例如，给出 n = 3，生成结果为：

[ "((()))", "(()())", "(())()", "()(())", "()()()" ]

解题思路

思路：回溯算法+剪枝；
根据上面的思路做减法，图解如下，假设 n = 2：

文章图片

从上面的图中，可以得出：

当左右括号可用数大于 0 时，可产生分支；
当左边尝试产生分支时，只需确认左括号可用数是否大于 0；
当右边尝试产生分支时，需要考虑左括号的可用数。这里仅当左括号可用数小于右括号可用数时，才能正常产生分支，否则需剪枝；
当左右括号可用数都等于 0 时，则表示结束。

代码实现

class Solution: def generateParenthesis(self, n: int) -> List[str]: res = [] cur_chr = ''def dfs(cur_chr, left, right): '''深度优化遍历Args: cur_chr: 当前递归得到的结果 left: 左括号能使用的个数 right: 右括号能使用的个数Returns: 返回所有可能的结果集 ''' # 当左右可用括号数为 0，添加到结果集返回 if left == 0 and right == 0: res.append(cur_chr) return # 如果左边的括号可用数大于右边，不符合设定，直接返回 if left > right: return # 左边括号可用数大于 0，添加左括号 if left > 0: dfs(cur_chr+'(', left-1, right) # 右边括号可用数大于 0，添加右括号 if right > 0: dfs(cur_chr+')', left, right-1)dfs(cur_chr, n, n) return res

实现结果