22. 括号生成
dfs+剪枝
本题使用dfs搜索，选(或者)两个分支。
观察出剪枝条件：不管进行到哪一位，(的数量都是>=)的，而且数量都不能超过n
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
void dfs(int i, int n, int left, int right, vector<string> &res,
string str) {
//剪枝条件
if (left < right || left > n)
return;
if (i >= 2 * n) {
res.push_back(str);
return;
}
str += '(';
dfs(i + 1, n, left + 1, right, res, str);
str[str.length() - 1] = ')';
dfs(i + 1, n, left, right + 1, res, str);
}
vector<string> generateParenthesis(int n) {
vector<string> res;
string str;
int left = 0, right = 0;
dfs(0, n, left, right, res, str);
return res;
}
};
int main() {
Solution s;
vector<string> res;
res = s.generateParenthesis(3);
for (int i = 0; i < res.size(); i++) {
cout << res[i] << endl;
}
cout << endl << res.size();
return 0;
}
