首页 > 代码库 > 022. Generate Parentheses

022. Generate Parentheses

 1 class Solution { 2 public: 3     vector<string> generateParenthesis(int n) { 4         vector<string> result; 5         string current; 6         string choice = "()"; 7         int numLeftBracket = 0; // 计数,左括号和右括号的差值,只需字符串中左括号的数量始终不小于右括号的数量,同时限制长度 8         dfs(result, choice, current, n, numLeftBracket); 9         return result;10     }11 private:12     void dfs(vector<string>& result, const string& choice, string& current, int n, int numLeftBracket)13     {14         if (numLeftBracket == 0 && current.size() == n * 2) {15             result.push_back(current);16             return;17         }18         else {19             if (numLeftBracket < 0 || numLeftBracket > n || current.size() > n * 2) return; // 这里需要注意限制current的长度20             else {21                 for (int i = 0; i < choice.size(); ++i) {22                     if (numLeftBracket > 0) {23                         current.push_back(choice[i]);24                         if (choice[i] == () dfs(result, choice, current, n, numLeftBracket + 1);25                         else dfs(result, choice, current, n, numLeftBracket - 1);26                     }27                     else {28                         if (choice[i] == )) continue;29                         else {30                             current.push_back(choice[i]);31                             dfs(result, choice, current, n, numLeftBracket + 1);32                         }33                     }34                     current.pop_back();35                 }36             }37         }38     }39 };

 

022. Generate Parentheses