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

糖逗

题目描述：

括号。设计一种算法，打印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[i] << endl; 
                cout << "------------------" << endl;
        }
        cout << endl;
        return 0;
} 

注意事项：
1.暂无。