一道DFS题目，两种写法，第二种是网上大神的写法。和别人的比起来真的是黯然失色o(╥﹏╥)o
#include<iostream> #include<algorithm> #include<string> #include<map> #include<vector> #include<iomanip> #include<stack> #include<queue> #include<unordered_set> #include<string.h> using namespace std; string temp; vector<string> reslt; int N; void dfs(int left, int right); vector<string> generateParenthesis(int n) { N = n; dfs(0, 0); return reslt; } void dfs(int left, int right) { if (right > left || left > N) return; if (left == N && right == N) { reslt.push_back(temp); return; } for (int i = 0; i < 2; i++) { if (i == 0) { temp.push_back('('); dfs(left + 1, right); temp.pop_back(); } else { temp.push_back(')'); dfs(left, right + 1); temp.pop_back(); } } return; } int main() { generateParenthesis(4); return 0; }别人的代码真的太简洁了，tql
#include<iostream> #include<algorithm> #include<string> #include<map> #include<vector> #include<iomanip> #include<stack> #include<queue> #include<unordered_set> #include<string.h> using namespace std; void generateParenthesisDFS(int left, int right, string out, vector<string> &res) { if (left > right) return; if (left == 0 && right == 0) res.push_back(out); else { if (left > 0) generateParenthesisDFS(left - 1, right, out + '(', res); if (right > 0) generateParenthesisDFS(left, right - 1, out + ')', res); } } vector<string> generateParenthesis(int n) { vector<string> res; generateParenthesisDFS(n, n, "", res); return res; } int main() { generateParenthesis(3); return 0; }
