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

糖逗

题目描述：

数字 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[2] = {"(", ")"};
    for(int i = 0; i < 2 ;i++){
        temp+=store[i];
        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[i] << " ";
        }
        cout << endl;
        return 0;
}

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