defgenerate_parenthesis(n: int) -> List[str]: if n == 0: return [''] result = {"()"} # 初始 n = 1,也就是唯一的结果 (),n 每增加 1,就多执行一次 for i in range(n-1): tmp = set() # 对每个结果都插入 for item in result: # 插入每个间隔位置 for i in range(len(item)+1): # 等于在每个间隔位置插入一对 () new_item = item[:i] + "()" + item[i:] tmp.add(new_item) # 这里每一轮结束后更新为最新的结果 result = tmp return list(result)
defvalid(A: list): res = 0 for e in A: if e == "(": res += 1 else: res -= 1 # 注意这个地方,只要中间有右括号的数量大于左括号的情况,肯定是无效的 if res < 0: returnFalse return res == 0 defgenerateParenthesis(n: int) -> list: defgenerate(A=[]): if len(A) == 2 * n: if valid(A): res.append("".join(A)) else: A.append("(") generate(A) A.pop() A.append(")") generate(A) A.pop() res = [] generate() return res
注意因为是 n-1 个,所以要 pop。生成给定 n 所有序列的复杂度是 O(2^2n),因为要生成所有的 n,所以还需要乘以 n,即:O(2^2n n)。
defgenerateParenthesis(n: int) -> list: defbacktrack(s='', left=0, right=0): if len(s) == 2*n: res.append(s) if left < n: backtrack(s+"(", left+1, right) if right < left: backtrack(s+")", left, right+1) res = [] backtrack() return res
defbinomial(n: int, k: int) -> int: # C(n,k) = C(n, n-k),减少计算量 if n-k < k: k = n - k # C(n, k) = A(n, k) / k! = n(n-1)...(n-k+1)/k! res = 1 for i in range(k): res *= (n-i) res /= (k+1) return res defcatalan(n: int): return binomial(2*n, n)/(n+1)
defgenerateParenthesis(n: int) -> list: if n == 0: return [''] res = [] for i in range(n): for left in generateParenthesis(i): for right in generateParenthesis(n-1-i): res.append("({}){}".format(left, right)) return res