C++刷leetcode（22. 括号生成）【深度优先搜索】
本帖最后由 糖逗 于 2020-5-8 17:58 编辑题目描述：
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例：
输入：n = 3
输出：[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
#include <iostream>
#include <vector>
#include <string>
using namespace std;
bool valid(string temp){
int count = 0;
for(char cha : temp){
if(count < 0) return false;
if(cha == '(')count ++;
if(cha == ')')count --;
}
return count == 0;
}
void dfs(int n, string temp, vector<string>& res){
if(temp.size() > n*2) return;
if(temp.size() == n*2 &&valid(temp)) res.push_back(temp);
string store = {"(", ")"};
for(int i = 0; i < 2 ;i++){
temp+=store;
dfs(n, temp, res);
temp.erase(temp.end()-1);
}
}
vector<string> generateParenthesis(int n) {
vector<string> res;
dfs(n, "(", res);
return res;
}
int main(void){
int number ;
cin >> number;
vector<string>res = generateParenthesis(number);
for(int i = 0; i < res.size(); i++){
cout << res << " ";
}
cout << endl;
return 0;
}
注意事项：
1.深度优先搜索，深度优先搜索的解题套路。
页:
[1]