07/04/2017
转一发一亩三分地上讲解的这类题目的一般套路：
所谓Backtracking都是这样的思路：在当前局面下，你有若干种选择。那么尝试每一种选择。如果已经发现某种选择肯定不行（因为违反了某些限定条件），就返回；如果某种选择试到最后发现是正确解，就将其加入解集
所以你思考递归题时，只要明确三点就行：选择 (Options)，限制 (Restraints)，结束条件 (Termination)。即“ORT原则”（这个是我自己编的）
对于这道题，在任何时刻，你都有两种选择：
- 加左括号。
- 加右括号。
同时有以下限制： - 如果左括号已经用完了，则不能再加左括号了。
- 如果已经出现的右括号和左括号一样多，则不能再加右括号了。因为那样的话新加入的右括号一定无法匹配。
结束条件是：
左右括号都已经用完。
结束后的正确性：
左右括号用完以后，一定是正确解。因为1. 左右括号一样多，2. 每个右括号都一定有与之配对的左括号。因此一旦结束就可以加入解集（有时也可能出现结束以后不一定是正确解的情况，这时要多一步判断）。
递归函数传入参数：
限制和结束条件中有“用完”和“一样多”字样，因此你需要知道左右括号的数目。
当然你还需要知道当前局面sublist和解集res。
因此，把上面的思路拼起来就是代码：
if (左右括号都已用完) {
加入解集，返回
}
//否则开始试各种选择
if (还有左括号可以用) {
加一个左括号，继续递归
}
if (右括号小于左括号) {
加一个右括号，继续递归
}
你帖的那段代码逻辑中加了一条限制：“3. 是否还有右括号剩余。如有才加右括号”。这是合理的。不过对于这道题，如果满足限制1、2时，3一定自动满足，所以可以不判断3。
这题其实是最好的backtracking初学练习之一，因为ORT三者都非常简单明显。你不妨按上述思路再梳理一遍，还有问题的话再说。
06/04/2017更新
昨天覃超提到了一种写法，里面没有用到「归去来兮」（也就是code ganker说的恢复现场），而是在参数里直接改变了构造结果的值。
我在弹幕上问，为什么没有做归去来兮？覃超解释说：
递归函数的参数本身就会进行归去来兮的还原
也可以手动归去来兮
如果是手动，中间变量就是全局共享的
否则是直接进行值拷贝又创建了一份
List<String> result = new ArrayList<>();
int num;
public List<String> generateParenthesis(int n) {
String sb = "";
num = n;
dfs(0, 0, sb);
return result;
}
public void dfs(int left, int right, String sb) {
if (left >= num && right >= num) {
result.add(sb);
return;
}
if (left < num) {
dfs(left + 1, right, sb + "(");
}
if (right < left) {
dfs(left, right + 1, sb + ")");
}
}
不过覃超也提到，用StringBuilder可以避免重复创建对象。具体可以看这里：http://www.jianshu.com/p/2c9e588def78
从前的版本
这个递归是不需要for循环的，总结一下就是，从0开始构造的递归是不需要for循环的。
另外想了很久为什么第一次打印((()))之后第二次会出栈4次，打印(()())，后来大概想明白了，因为前三次backtracking之后sb.deleteCharAt(sb.length() - 1);执行完了就没东西执行了，所以开始执行if (left < n)里面的backtracking。
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
StringBuilder sb = new StringBuilder();
dfs(0, 0, result, sb, n);
return result;
}
public void dfs(int left, int right, List<String> result, StringBuilder sb, int n) {
if (left >= n && right >= n) {
result.add(sb.toString());
return;
}
if (left < n) {
sb.append("(");
dfs(left + 1, right, result, sb, n);
sb.deleteCharAt(sb.length() - 1);
}
if (right < left) {
sb.append((")"));
dfs(left, right + 1, result, sb, n);
sb.deleteCharAt(sb.length() - 1);
}
}
ref:
http://blog.csdn.net/ymrfzr/article/details/51201934
http://www.jianshu.com/p/2c9e588def78
