C++刷leetcode(面试题 08.09. 括号）【深度优先搜索】

糖逗

题目描述：

1. 
   
2. 括号。设计一种算法，打印n对括号的所有合法的（例如，开闭一一对应）组合。
   
3. 
   
4. 说明：解集不能包含重复的子集。
   
5. 
   
6. 例如，给出 n = 3，生成结果为：
   
7. 
   
8. [
   
9.   "((()))",
   
10.   "(()())",
    
11.   "(())()",
    
12.   "()(())",
    
13.   "()()()"
    
14. ]

复制代码

1. #include <string>
   
2. #include <vector>
   
3. #include <set>
   
4. #include <iostream>
   
5. 
   
6. using namespace std;
   
7. 
   
8. 
   
9. bool valid(string input){
   
10.     int count = 0;
    
11.     for(char temp:input){
    
12.         if(temp == '(')count ++;
    
13.         if(temp == ')'){
    
14.             count--;
    
15.             if(count < 0) return false;
    
16.         }
    
17.     }
    
18.     return count == 0;
    
19. }
    
20. 
    
21. void dfs(int n, set<string>& res, string temp){
    
22.     if(temp.size() > 2*n) return;
    
23.     if(temp.size() == 2*n && valid(temp)) res.insert(temp);
    
24.     vector<char> t {'(', ')'};
    
25.     for(auto c : t){
    
26.         temp += c;
    
27.         dfs(n, res, temp);
    
28.         temp.pop_back();
    
29.     }
    
30.    
    
31. }
    
32. 
    
33. vector<string> solution(int n) {
    
34.     set<string> res;
    
35.     dfs(n, res, "");
    
36.     vector<string> out(res.begin(), res.end());
    
37.     return out;
    
38. }
    
39. 
    
40. int main(void){
    
41.         int number;
    
42.         cin >> number;
    
43.         vector<string> res = solution(number);
    
44.         for(int i = 0; i < res.size(); i++){
    
45.                 cout << res[i] << endl;
    
46.                 cout << "------------------" << endl;
    
47.         }
    
48.         cout << endl;
    
49.         return 0;
    
50. }

复制代码

注意事项：
1.暂无。