C++刷leetcode（22. 括号生成）【深度优先搜索】

糖逗

题目描述：

1. 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
   
2. 
   
3.  
   
4. 
   
5. 示例：
   
6. 
   
7. 输入：n = 3
   
8. 输出：[
   
9.        "((()))",
   
10.        "(()())",
    
11.        "(())()",
    
12.        "()(())",
    
13.        "()()()"
    
14.      ]
    
15. 
    
16. 来源：力扣（LeetCode）
    
17. 链接：https://leetcode-cn.com/problems/generate-parentheses
    
18. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

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

复制代码

注意事项：
1.深度优先搜索，深度优先搜索的解题套路。