22. 括号生成

描述

• 给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

示例

  给出 n = 3，生成结果为：
    [
      "((()))",
      "(()())",
      "(())()",
      "()(())",
      "()()()"
    ]

思路

1. 暴力法，利用回溯列出全排列，然后筛选其中符合条件的组合返回。思路较为简单，但效率比较低。不过其中回溯算法的写法和判断括号是否有效要掌握。
2. 仔细思考暴力法中回溯的过程，很多时候在添加‘('或者')'的时候就已经能够知道是否合法了，所以应该只回溯合法的组合，回溯到最后即可加入到结果集中：
   1）对于数字 n，一共有 n 个 '(' 和 n 个')'
   2）对于结果集中的一个位置str[i]，左括号总是可以加入的(只要还有剩余)，而右括号只有在前面有多余的左括号的情况下才可以加入。因此可以利用一个 notCouple 变量记录未配对的个数，加入左括号时+1，加入右括号时-1。
   3）接口设计为helper(当前位置，总长度，剩余左括号数，剩余右括号数，当前未配对数，当前字符串，结果集)

class Solution_22_01 {
 public:
  vector<string> generateParenthesis(int n) {
    if (n < 1) return {};
    string str = "";
    vector<string> ret;
    _generateParenthesis(0, n * 2, str, ret);
    return ret;
  }
  void _generateParenthesis(int n, int size, string& str, vector<string>& ret) {
    if (n == size) {
      if (isValidBracket(str)) ret.push_back(str);
      return;
    }
    str.push_back('(');
    _generateParenthesis(n + 1, size, str, ret);
    str.pop_back();
    str.push_back(')');
    _generateParenthesis(n + 1, size, str, ret);
    str.pop_back();
  }
  bool isValidBracket(string str) {
    stack<char> ms;
    for (char ch : s) {
      if (ch == '(')
        ms.push(ch);
      else if (ch == ')') {
        if (ms.empty() || ms.top() != '(') return false;
        ms.pop();
      }
    }
    return ms.empty();
  }
};

class Solution_22_02 {
 public:
  vector<string> generateParenthesis(int n) {
    if (n < 1) return {};
    vector<string> ret;
    string str;
    helper(0, n * 2, n, n, 0, str, ret);
    return ret;
  }
  void helper(int n, int size, int left, int right, int notCouple, string& str,
              vector<string>& ret) {
    if (n == size) {
      ret.push_back(str);
      return;
    }
    if (left > 0) {
      str.push_back('(');
      helper(n + 1, size, left - 1, right, notCouple + 1, str, ret);
      str.pop_back();
    }
    if (right > 0 && notCouple > 0) {
      str.push_back(')');
      helper(n + 1, size, left, right - 1, notCouple - 1, str, ret);
      str.pop_back();
    }
  }
};