Python面试宝典第25题：括号生成

不风不疯

题目        数字n代表生成括号的对数，请设计一个函数，用于能够生成所有可能的并且有效的括号组合。        备注：10），则在当前序列后添加一个左括号，然后递归调用自身，减小left的计数。        4、递归生成右括号。如果右括号的数量少于等于左括号（right0:backtrack(left-1,right,curr_str+'(',result)ifright>left:backtrack(left,right-1,curr_str+')',result)result=[]backtrack(n,n,'',result)returnresultprint(generate_brackets_by_recursion(3))print(generate_brackets_by_recursion(1))总结        递归法求解本题的时间复杂度主要取决于生成的括号组合的数量。对于n对括号，有效的括号组合数量遵循卡特兰数，其公式为C_n=(1/(n+1))*(2nchoosen)。卡特兰数的增长速度非常快，大约是4^n/(sqrt(pi*n)*n^(3/2))。因此，时间复杂度为O(C_n)，即：O(4^n/sqrt(n))。空间复杂度主要由递归栈的深度决定，最坏情况下，递归栈的深度为2n，故空间复杂度为O(n)。        递归法特别适合括号生成类问题，因为它能自然地表达出问题的结构，即通过逐步构建解的空间树来寻找所有可能的解。然而，当n接近上限（比如：n=8）时，生成的组合数量会非常庞大，这可能会对程序的执行时间和内存使用提出较高的要求。因此，在实际应用中需要考虑递归的深度和效率问题。💡需要《Python面试宝典》完整源码的大佬们，可订阅专栏后，搜索微信公众号“希望睿智”私信获取。