链接
https://leetcode.cn/problems/generate-parentheses/description/
分析
这个题目是让生成有效的括号组合，首先我们搞明白一个问题，什么叫有效的括号？
1. 所有的括号都能找到有效的闭合。
基于此，我们可以认为：左括号数等于右括号数，且从左往后遍历一个序列，已经遍历过的序列中，左括号数始终都大于等于右括号数。 这样才能使所有的括号都能找到有效的闭合。
基于此，我们可以想到2个办法：
1. 我们通过DFS，生成固定长度的所有序列，如果它符合条件，那么我们把它加入到结果值中。
2. 我们通过动态规划的方式。想一个最基本的场景，对于一个有效闭合的序列，我们去给他加一对括号："()"，别管这个括号加在哪个位置，新生成的序列都为有效括号，所以基于此我们可以进行推导。
代码一-DFS
class Solution: def generateParenthesis(self, n: int): res = [] def dfs(left_count, right_count, depth, cur): if depth == n*2: if left_count == right_count: res.append(cur) return if left_count < right_count: # 剪枝 return dfs(left_count+1, right_count, depth+1, cur+'(') dfs(left_count, right_count+1, depth+1, cur+')') dfs(0, 0, 0, '') return res
代码二-动态规划
class Solution: def generateParenthesis(self, n: int): res = ['()'] visited = set(res) for i in range(2, n+1): cur_res = [] for s in res: for j in range(len(s)+1): tmp_s = s[:j] + '()' + s[j:] if tmp_s not in visited: visited.add(tmp_s) cur_res.append(tmp_s) res = cur_res return res