【Hot 100 刷题计划】 LeetCode 22. 括号生成 | C++ DFS 回溯与极致剪枝

LeetCode 22. 括号生成 题目描述题目级别中等数字n代表生成括号的对数请你设计一个函数用于能够生成所有可能的并且有效的括号组合。示例 1:输入n 3输出[((())),(()()),(())(),()(()),()()()]示例 2:输入n 1输出[()] 破题思路DFS 决策树与合法性剪枝生成括号的过程本质上就是不断地做选择当前位置是放(还是放)如果我们不加限制地乱放长度为2n的字符串会产生22n2^{2n}22n种组合然后再去写一个验证函数来剔除不合法的组合效率会极低。最高效的做法是在生成DFS 下探的过程中就直接剪除掉不合法的分支。如何保证生成的括号一定是合法的只需牢记两条铁律随时可以加左括号只要已放置的左括号数量u还没达到总对数n就可以继续加左括号。加右括号必须有前提只有当已放置的左括号数量u严格大于已放置的右括号数量v时才能放置右括号。否则就会出现())(这种无法挽回的非法闭合。 C 代码实现 (极简传值法)classSolution{public:vectorstringres;vectorstringgenerateParenthesis(intn){string str;// 初始状态左括号 0 个右括号 0 个空字符串限制为 ndfs(0,0,str,n);returnres;}voiddfs(intu,intv,string str,intn){// 递归终止条件字符串长度达到 2 * n说明一对对括号全放满了if(str.size()2*n){res.push_back(str);return;}// 核心剪枝条件 1左括号还没用完就可以尽情加左括号if(un){// 注意参数里直接写 str (隐式完成了字符串拷贝// 使得当前层的 str 变量不会被破坏巧妙省去了手动 pop_back 的回溯代码。dfs(u1,v,str(,n);}// 核心剪枝条件 2左括号比右括号多才能放右括号去闭合它if(uv){dfs(u,v1,str),n);}}};