【LetMeFly】22.括号生成暴力枚举 / 回溯力扣题目链接https://leetcode.cn/problems/generate-parentheses/数字n代表生成括号的对数请你设计一个函数用于能够生成所有可能的并且有效的括号组合。示例 1输入n 3输出[((())),(()()),(())(),()(()),()()()]示例 2输入n 1输出[()]提示1 n 8解题方法一暴力枚举二进制状态压缩n nn对括号组成的字符串长度2 n 2n2n我们枚举长度为2 n 2n2n的字符串所有的2 2 n 2^{2n}22n种左右括号的可能如果是合法括号序列则加入答案中。时间复杂度O ( 4 n × n ) O(4^{n}\times n)O(4n×n)。共有2 2 n 2^{2n}22n种可能每种可能需要O ( n ) O(n)O(n)的时间去判断是否合法。不过实际上会有很多状态提前退出枚举。空间复杂度O ( n ) O(n)O(n)空间复杂度来自临时构造的字符串力扣返回值不计入算法空间复杂度。AC代码C/* * LastEditTime: 2026-10-02 16:43:41 */classSolution{public:vectorstringgenerateParenthesis(intn){vectorstringans;n*2;for(inti0,to1n;ito;i){strings(n,0);booloktrue;intcnt_left0;for(intj0;jn;j){if(ij1){cnt_left;s[j](;}elseif(!cnt_left){okfalse;break;}else{cnt_left--;s[j]);}}if(cnt_left){continue;}if(ok){ans.push_back(s);}}returnans;}};解题方法二回溯写一个函数dfs尝试字符串当前位置的每一种可能。dfs接收参数s, idx, diff, left, right表示字符串当前应该填充s[idx]位置还有left个左括号和right个右括号当前左括号比右括号多diff个。如果left和right都为0说明已经填充完毕加入答案中。如果left非零可尝试填充左括号。如果diff非零且right非零可尝试填充右括号。以上。时间复杂度O ( 4 n ) O(4^{n})O(4n)。实际上只会枚举所有合法括号序列。空间复杂度O ( n ) O(n)O(n)临时构造的字符串、最大递归深度的空间复杂度都是O ( n ) O(n)O(n)力扣返回值不计入算法空间复杂度。AC代码C/* * LastEditTime: 2026-10-02 16:54:44 */classSolution{private:vectorstringans;voiddfs(strings,intidx,intdiff,intleft,intright){if(!left!right){ans.push_back(s);}if(left){s[idx](;dfs(s,idx1,diff1,left-1,right);}if(diffright){s[idx]);dfs(s,idx1,diff-1,left,right-1);}}public:vectorstringgenerateParenthesis(intn){strings(n*2, );dfs(s,0,0,n,n);returnans;}};同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~千篇源码题解已开源