LeetCode 22. 括号生成 的 Python3 实现classSolution:defgenerateParenthesis(self,n:int)-List[str]:res[]defbacktrack(s,left,right):# 如果左右括号都用完了得到一个有效组合iflen(s)2*n:res.append(s)return# 还可以放左括号ifleftn:backtrack(s(,left1,right)# 还可以放右括号前提右括号数量 左括号数量ifrightleft:backtrack(s),left,right1)backtrack(,0,0)returnres解题思路回溯法DFSleft已使用的左括号数量right已使用的右括号数量剪枝条件放左括号left n左括号还没用完放右括号right left只有右括号少于左括号时才能放保证有效性终止条件 字符串长度达到2n时得到一个有效组合。复杂度时间第 n 个卡特兰数 C_n \frac{1}{n1}\binom{2n}{n}即有效组合的数量回溯过程每个有效解需要 O(n) 时间构建总体 O(n \cdot C_n)空间递归栈深度 O(n)结果空间 O(n \cdot C_n) Kimi LeetCode 22. 括号生成 Python3实现
LeetCode 22. 括号生成 的 Python3 实现classSolution:defgenerateParenthesis(self,n:int)-List[str]:res[]defbacktrack(s,left,right):# 如果左右括号都用完了得到一个有效组合iflen(s)2*n:res.append(s)return# 还可以放左括号ifleftn:backtrack(s(,left1,right)# 还可以放右括号前提右括号数量 左括号数量ifrightleft:backtrack(s),left,right1)backtrack(,0,0)returnres解题思路回溯法DFSleft已使用的左括号数量right已使用的右括号数量剪枝条件放左括号left n左括号还没用完放右括号right left只有右括号少于左括号时才能放保证有效性终止条件 字符串长度达到2n时得到一个有效组合。复杂度时间第 n 个卡特兰数 C_n \frac{1}{n1}\binom{2n}{n}即有效组合的数量回溯过程每个有效解需要 O(n) 时间构建总体 O(n \cdot C_n)空间递归栈深度 O(n)结果空间 O(n \cdot C_n)