22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。 示例：

  1. 输入：n = 3
  2. 输出：[
  3.     "((()))",
  4.     "(()())",
  5.     "(())()",
  6.     "()(())",
  7.     "()()()"
  8.   ]

代码实现

  1. /*
  2. 方法一还有改进的余地：我们可以只在序列仍然保持有效时才添加 '(' or ')'，而不是像 方法一 那样每次添加。我们可以通过跟踪到目前为止放置的左括号和右括号的数目来做到这一点，
  4. 如果左括号数量不大于 nnn，我们可以放一个左括号。如果右括号数量小于左括号的数量，我们可以放一个右括号。
  6. */
  7. class Solution {
  9.     void generate_all(string& current,int leftNums, int rightNums,int n, vector<string>& result) {
  10.         if (n*2 == current.size()) {
  11.             result.push_back(current);
  12.             return;
  13.         }
  14.         if(leftNums < n){
  15.             current += '(';
  16.             generate_all(current,leftNums+1,rightNums, n, result);
  17.             current.pop_back();
  18.         }
  19.         if(rightNums < leftNums ){
  20.             current += ')';
  21.             generate_all(current,leftNums,rightNums+1, n, result);
  22.             current.pop_back();
  23.         }
  25.     }
  26. public:
  27.     vector<string> generateParenthesis(int n) {
  28.         vector<string> result;
  29.         string current;
  30.         generate_all(current, 0, 0, n, result);
  31.         return result;
  32.     }
  33. };