括号生成-回溯法

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

示例：

输入：n = 3
输出：[
       "((()))",
       "(()())",
       "(())()",
       "()(())",
       "()()()"
     ]

题解

回溯法是暴力搜索法中的一种。 对于某些计算问题而言，回溯法是一种可以找出所有解的一般性算法，尤其适用于约束满足问题。 在经典的教科书中，八皇后问题展示了回溯法的用例。 回溯法采用试错的思想，它尝试分步的去解决一个问题。 维基百科

这道题使用回溯法，出口条件是左右括号数目相等且等于n，当左括号大于n或者右括号大于左括号时，回退。相当于暴力法穷尽所有情况，但只输出满足出口条件的情况。

/*
   回溯法,列举所有可能情况找到答案
   1.当左括号小于n时,放入左括号
   2.当右括号小于左括号时,放入右括号

*/
// @lc code=start
class Solution {
 public:
  void dfs(vector<string> &ans, string str, int lc, int rc, int n) {
    if (lc > n || rc > lc) return;
    if (lc == rc && lc == n) {
      ans.push_back(str);
      return;
    }
    dfs(ans, str + '(', lc + 1, rc, n);
    dfs(ans, str + ')', lc, rc + 1, n);
  }
  vector<string> generateParenthesis(int n) {
    vector<string> ans;
    int lc,rc;
    lc=rc=0;
    dfs(ans,"",lc,rc,n);
    return ans;
  }
};
// @lc code=end

还可以将string和ans作为全局变量存储，但要在执行完一步后回退到上一个状态。

/*
 * @lc app=leetcode.cn id=22 lang=cpp
 *
 * [22] 括号生成
 */
/*
   1.左括号小于右括号  加入左括号
   2.右括号小于左括号,压入右括号
   3.输出条件: 长度为2*n,且右括号等于左括号
   4.退出条件 :左括号大于n或者右括号大于左括号

*/
// @lc code=start
class Solution {
 public:
  string str;
  vector<string> ans;
  void dfs(int lc, int rc, int n) {
    if (lc < rc || lc > n) {
      return;
    }
    if (lc == rc && lc == n) {
      ans.push_back(str);
      return;
    }
    if (lc < n) {
      str += '(';
      dfs(lc + 1, rc, n);
      str.pop_back();   //回退
    }
    if (rc < lc) {
      str += ')';
      dfs(lc, rc + 1, n);
      str.pop_back();  //回退
    }
  }
  vector<string> generateParenthesis(int n) {
    dfs(0, 0, n);
    return ans;
  }
};
// @lc code=end

其实我对于回退的理解在于回溯法更像是进入了一个平行世界，比如下面这个片段

 if (lc < n) {
      str += '(';
      dfs(lc + 1, rc, n);
      str.pop_back();   //回退
    }

dfs进入下一层递归，而下一层又会进入下一层。。。从而找出所有情况。而对于当前层的函数来说，dfs只进行了一步操作。所以要取消这一步操作的结果，继续进行其他操作（注意这里的取消是指在公共的空间内取消自己占用的当前层空间，因为所有层公用一个str）。