给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
例如，给出 n = 3，生成结果为：
[ “((()))”, “(()())”, “(())()”, “()(())”, “()()()” ]
看题解写的回溯法，时间和我自己写的暴力法也没啥区别啊
class Solution(object): def generateParenthesis(self, n): """ :type n: int :rtype: List[str] """ res = [] def gen(s = '', left = 0, right = 0): if left == right == n and s: # 只有当s平衡且有3对括号才写入结果 res.append(s) if left <= n: gen(s + '(', left+1, right) if right < left: gen(s + ')', left, right+1) gen() return res暴力解法 右括号插入的地方是左括号插入的index+1 然后取set去重 这里也可以降内存的，就是不需要维护长度为n的res，直接维护n-1和n的就行
class Solution(object): def generateParenthesis(self, n): """ :type n: int :rtype: List[str] """ if n == 0: return None res = [[]] * n if n == 1: return ['()'] res[0] = ['()'] c = 2 while c <= n: tmp_res = [] for e in res[c-2]: #e is the pattern from last step idx_left = 2 * (c-1) idx_right = 2 * c for idx1 in range(idx_left + 1): tmp = e tmp = e[:idx1] + '(' + e[idx1:] for idx2 in range(idx1+1, idx_right): r = tmp[:idx2] + ')' + tmp[idx2:] tmp_res.append(r) res[c-1] = set(tmp_res) c += 1 return res[-1]