训练题：有效括号组合

题目：https://leetcode-cn.com/problems/generate-parentheses/

排列组合首先想到回溯算法。

  2. vector<string> generateParenthesis(int n) {
  3.     if(n == 1) return {"()"};
  5.     vector<string> ret;
  6.     string str("(");
  8.     str.reserve(n<<1);
  10.     int left = 1, right = 0;
  11.     backtrack(ret, str, left, right, n);
  13.     return ret;
  14. }
  16. // 使用引用，减少中间变量
  17. // left:        str中(的数量
  18. // right:        str中)的数量
  19. // maxCount:    括号对数
  20. void backtrack(vector<string>& vec, string& str, int& left, int& right, const int& maxCount){
  21.     if(left == maxCount && right == maxCount){
  22.         vec.push_back(str);
  23.         return;
  24.     }
  26.     // 左括号(已经用完，往后全都必须是右括号，单独拿出来处理，减少递归深度。
  27.     if(left == maxCount) {
  28.         int tmp = maxCount - right;
  29.         str.append(tmp, ')');            // 补齐剩下的括号
  30.         vec.push_back(str);
  31.         str.resize(str.size()-tmp);        // 恢复到补齐之前的内容
  32.         return;
  33.     }
  35.     // 左括号还没有满的时候，就可以添加左括号
  36.     if(left < maxCount) {
  37.         str.push_back('(');
  38.         select(vec, str, ++left, right, maxCount);
  39.         str.pop_back();
  40.         --left;
  41.     }
  43.     // 右括号比左括号少的时候，就可以添加右括号
  44.     if(right < left) {
  45.         str.push_back(')');
  46.         select(vec, str, left, ++right, maxCount);
  47.         str.pop_back();
  48.         --right;
  49.     }
  50. }

训练题：数字组合

语雀内容

训练题：1到n（全排列）

语雀内容

训练题：字符串排列

语雀内容