LeetCode解题技巧:深度优先搜索、广度优先搜索、回溯法与剪枝 - C++实现 专题2:生成括号
最编程
2024-02-29 14:26:13
...
1、题目描述
leetcode链接
2、代码
class Solution
{
public:
// 1、全局变量
string path;
vector<string> ret;
int right = 0, left = 0, n = 0;
vector<string> generateParenthesis(int _n)
{
n = _n;
dfs();
return ret;
}
void dfs()
{
// 1、出口
if(right == n)
{
ret.push_back(path);
return;
}
// 2、添加左括号
if(left < n)
{
path.push_back('(');
left++;
dfs();
path.pop_back(); // 恢复现场
left--;
}
if(right < left) // 3、添加右括号
{
path.push_back(')');
right++;
dfs();
path.pop_back(); // 恢复现场
right--;
}
}
};