C++刷leetcode(面试题 08.09. 括号）【深度优先搜索】
本帖最后由 糖逗 于 2020-5-8 17:51 编辑题目描述：
括号。设计一种算法，打印n对括号的所有合法的（例如，开闭一一对应）组合。
说明：解集不能包含重复的子集。
例如，给出 n = 3，生成结果为：
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
#include <string>
#include <vector>
#include <set>
#include <iostream>
using namespace std;
bool valid(string input){
int count = 0;
for(char temp:input){
if(temp == '(')count ++;
if(temp == ')'){
count--;
if(count < 0) return false;
}
}
return count == 0;
}
void dfs(int n, set<string>& res, string temp){
if(temp.size() > 2*n) return;
if(temp.size() == 2*n && valid(temp)) res.insert(temp);
vector<char> t {'(', ')'};
for(auto c : t){
temp += c;
dfs(n, res, temp);
temp.pop_back();
}
}
vector<string> solution(int n) {
set<string> res;
dfs(n, res, "");
vector<string> out(res.begin(), res.end());
return out;
}
int main(void){
int number;
cin >> number;
vector<string> res = solution(number);
for(int i = 0; i < res.size(); i++){
cout << res << endl;
cout << "------------------" << endl;
}
cout << endl;
return 0;
}
注意事项：
1.暂无。
页:
[1]