力扣HOT100之回溯：22. 括号生成
这道题自己A的，我用的思路比较简单，我们额外定义一个辅助函数isValid，用于判断输入的括号字符是否是闭合的，这个用栈来实现很简单，对应的问题可以参考20.有效的括号，这里不过多描述。我们还需要定义一个递归函数进行回溯，我们只需要选择在path末尾添加'('或者')'，然后再进入下一层递归即可，当递归结束后，及时将字符串末尾的字符移除。当path的长度达到2 * n时，我们就可以判断当前的path是否为合法结果，调用isValid判断即可，如果合法，就将其加入到result数组中，否则直接返回。但是我这个办法用时太长了，感觉还有可以优化的地方。
class Solution {
public:string path; vector<string> result;vector<char> brackets = {'(', ')'};//判断括号是否有效bool isValid(string& s){stack<char> st;for(char c : s){if(c == '(') st.push(c);else{if(!st.empty() && st.top() == '(') //必须要先判断栈是否为空，否则会报错st.pop();else return false;}}return st.empty();}vector<string> generateParenthesis(int n) {backtracking(n);return result;}//回溯函数void backtracking(int n){//递归终止条件if(path.size() == 2 * n){if(isValid(path)) //收集正确结果result.emplace_back(path);return ;}//递归主体for(int i = 0; i < brackets.size(); i++){path += brackets[i];backtracking(n);path.pop_back();}}
};
我看了下灵神的题解，感觉他的思路挺好的，强烈建议看一下他的题解以及配套视频，灵神的思路就是提前定义一个长度为2 * n的字符串，然后用递归函数遍历所有位置，判断每个位置填左括号还是右括号，当处理完所有位置时，就将结果添加到向量中，当然，每个位置上的左右括号并不是任意填的，无论填入左括号还是右括号，都需要满足一定的条件。
假设现在已经填了i个括号，那么下标从0到i - 1都已经填过了，我们需要讨论在下标为i的位置上应该填什么括号。假设现在已经填了open个左括号，那么已填的右括号的数量为i - open个。
- 当
open < n时，表明当前位置还可以填左括号，因为要填出n对括号，一定是n个左括号和n个右括号，只要左括号的额度还没完，就可以一直填，不需要关注已填的括号是否都闭合。当第i个位置填入左括号时，path[i] = '(';，并递归调用dfs(i + 1, open + 1)。 - 当
open > i - open时，表明当前位置可以填右括号，在已填的括号中，右括号的数量绝对不能超过左括号，要不然就是非法结果。当第i个位置填入右括号时，path[i] = ')';，并递归调用dfs(i + 1, open)。
用灵神的思路写出来的代码果然速度快了很多，其原因是对枚举结果进行了剪枝，通过加入左右括号的填入限制条件，避免了很多错误的结果，保证触发递归终止条件时，收获的结果一定是合法结果。
class Solution {
public:vector<string> generateParenthesis(int n) {int m = n * 2; //左括号 + 右括号的总长度vector<string> ans;string path(m, 0);// 目前填了 i 个括号// 这 i 个括号中有 open 个左括号，i-open 个右括号// 就是在此基础上，最多还能再填balance个')'auto dfs = [&](this auto&& dfs, int i, int open) {//递归终止条件if(i == m){ //括号构造完毕，收获结果(结果一定是对的)ans.emplace_back(path);return ;}//递归主体逻辑//枚举当前位置填左括号还是右括号//可以填左括号if(open < n){//填左括号path[i] = '(';dfs(i + 1, open + 1);}//可以填右括号if(i - open < open){//填右括号path[i] = ')';dfs(i + 1, open);}};dfs(0, 0);return ans;}
};