本文目录 ⌄
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例：
输入：n = 3
输出：[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]题解
回溯法是暴力搜索法中的一种。 对于某些计算问题而言，回溯法是一种可以找出所有解的一般性算法，尤其适用于约束满足问题。 在经典的教科书中，八皇后问题展示了回溯法的用例。 回溯法采用试错的思想，它尝试分步的去解决一个问题。 维基百科
这道题使用回溯法，出口条件是左右括号数目相等且等于n，当左括号大于n或者右括号大于左括号时，回退。相当于暴力法穷尽所有情况，但只输出满足出口条件的情况。
/*
回溯法,列举所有可能情况找到答案
1.当左括号小于n时,放入左括号
2.当右括号小于左括号时,放入右括号
*/
// @lc code=start
class Solution {
public:
void dfs(vector<string> &ans, string str, int lc, int rc, int n) {
if (lc > n || rc > lc) return;
if (lc == rc && lc == n) {
ans.push_back(str);
return;
}
dfs(ans, str + '(', lc + 1, rc, n);
dfs(ans, str + ')', lc, rc + 1, n);
}
vector<string> generateParenthesis(int n) {
vector<string> ans;
int lc,rc;
lc=rc=0;
dfs(ans,"",lc,rc,n);
return ans;
}
};
// @lc code=end
还可以将string和ans作为全局变量存储，但要在执行完一步后回退到上一个状态。
/*
* @lc app=leetcode.cn id=22 lang=cpp
*
* [22] 括号生成
*/
/*
1.左括号小于右括号 加入左括号
2.右括号小于左括号,压入右括号
3.输出条件: 长度为2*n,且右括号等于左括号
4.退出条件 :左括号大于n或者右括号大于左括号
*/
// @lc code=start
class Solution {
public:
string str;
vector<string> ans;
void dfs(int lc, int rc, int n) {
if (lc < rc || lc > n) {
return;
}
if (lc == rc && lc == n) {
ans.push_back(str);
return;
}
if (lc < n) {
str += '(';
dfs(lc + 1, rc, n);
str.pop_back(); //回退
}
if (rc < lc) {
str += ')';
dfs(lc, rc + 1, n);
str.pop_back(); //回退
}
}
vector<string> generateParenthesis(int n) {
dfs(0, 0, n);
return ans;
}
};
// @lc code=end
其实我对于回退的理解在于回溯法更像是进入了一个平行世界，比如下面这个片段
if (lc < n) {
str += '(';
dfs(lc + 1, rc, n);
str.pop_back(); //回退
}dfs进入下一层递归，而下一层又会进入下一层。。。从而找出所有情况。而对于当前层的函数来说，dfs只进行了一步操作。所以要取消这一步操作的结果，继续进行其他操作（注意这里的取消是指在公共的空间内取消自己占用的当前层空间，因为所有层公用一个str）。