LeetCode：Generate Parentheses

题目链接为Generate Parentheses，这道题我思考了不少的时间，其实解题思路是比较清晰，但就是写不出相应的代码来。这可能就是传说中真正的编程能力吧，把思想转化为代码。

这道题直观的解法就是回溯法，题目描述的时候relate topics也写的有backtracking，所以我一开始的思路就是用-1代表左括号，+1代表右括号，定义一个长度为2*n的数组，从左往右遍历数组，先给相应位置上赋值为-1，检查是不是符合要求（满足要求的时所有数组元素的和小于等于0且大于等于-n），这样从左到右遍历就能得到结果。输出的时候再把-1和+1转化为左括号和右括号就可以。

我之所以没有写出代码来，是因为卡在了不知道如何表达回溯这个做法。看了别人的解法，发现回溯其实可以用递归来表示（不知道这样表述正不正确？），比如下面的代码既可以称为递归也可以称为回溯，并且是正确的代码。

class Solution {
public:
  vector<string> generateParenthesis(int n) {
    vector<string> res;
    generateParenthesisDFS(n, n, "", res);
    return res;
  }

  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);
    }
  }
}

这个解法用left和right两个变量分别表示剩余可以用的左括号和右括号的个数，然后用DFS的方法遍历解空间并且使用了剪枝（generateParenthesisDFS第一个if语句处是对解空间的剪枝，避免了很多无效的枚举）。

另一种解法也是在相同的博客中发现的，技巧性的比较强,，此处贴出代码。

class Solution {
public:
  vector<string> generateParentheses(int n) {
    set<string> t;
    if(n == 0)  t.insert("");
    else {
      vector<string> pre = generateParentheses(n-1);
      for(auto a : pre) {
        for(int i = 0; i < a.size(); ++i) {
          if(a[i] == '(') {
            a.insert(a.begin()+i+1, '(');
            a.insert(a.begin()+i+2, ')');
            t.insert(a);
            a.erase(a.begin()+i+1, a.begin()+1+3);
          }
        }
        t.insert("()" + a);
      }
    }
    return vector<string>(t.begin(), t.end());
  }
}

其主要思想就是在已有结果中每个左括号后面添加一对括号，然后再在头部添加一对括号，这样就能得到所有的结果。
参考博客：
https://www.cnblogs.com/grandyang/p/4444160.html