07/04/2017
轉(zhuǎn)一發(fā)一畝三分地上講解的這類題目的一般套路：
所謂Backtracking都是這樣的思路：在當(dāng)前局面下杭隙，你有若干種選擇哟绊。那么嘗試每一種選擇。如果已經(jīng)發(fā)現(xiàn)某種選擇肯定不行（因為違反了某些限定條件）痰憎，就返回票髓；如果某種選擇試到最后發(fā)現(xiàn)是正確解，就將其加入解集
所以你思考遞歸題時信殊，只要明確三點就行：選擇 (Options)炬称，限制 (Restraints)，結(jié)束條件 (Termination)涡拘。即“ORT原則”（這個是我自己編的）
對于這道題玲躯，在任何時刻，你都有兩種選擇：
- 加左括號。
- 加右括號跷车。
同時有以下限制： - 如果左括號已經(jīng)用完了棘利，則不能再加左括號了。
- 如果已經(jīng)出現(xiàn)的右括號和左括號一樣多朽缴，則不能再加右括號了善玫。因為那樣的話新加入的右括號一定無法匹配。
結(jié)束條件是：
左右括號都已經(jīng)用完密强。
結(jié)束后的正確性：
左右括號用完以后茅郎，一定是正確解。因為1. 左右括號一樣多或渤，2. 每個右括號都一定有與之配對的左括號系冗。因此一旦結(jié)束就可以加入解集（有時也可能出現(xiàn)結(jié)束以后不一定是正確解的情況，這時要多一步判斷）薪鹦。
遞歸函數(shù)傳入?yún)?shù)：
限制和結(jié)束條件中有“用完”和“一樣多”字樣掌敬，因此你需要知道左右括號的數(shù)目。
當(dāng)然你還需要知道當(dāng)前局面sublist和解集res池磁。
因此奔害，把上面的思路拼起來就是代碼：
if (左右括號都已用完) {
加入解集，返回
}
//否則開始試各種選擇
if (還有左括號可以用) {
加一個左括號地熄，繼續(xù)遞歸
}
if (右括號小于左括號) {
加一個右括號华临，繼續(xù)遞歸
}
你帖的那段代碼邏輯中加了一條限制：“3. 是否還有右括號剩余。如有才加右括號”端考。這是合理的银舱。不過對于這道題，如果滿足限制1跛梗、2時寻馏，3一定自動滿足，所以可以不判斷3核偿。
這題其實是最好的backtracking初學(xué)練習(xí)之一诚欠，因為ORT三者都非常簡單明顯。你不妨按上述思路再梳理一遍漾岳，還有問題的話再說轰绵。
06/04/2017更新
昨天覃超提到了一種寫法，里面沒有用到「歸去來兮」（也就是code ganker說的恢復(fù)現(xiàn)場）尼荆，而是在參數(shù)里直接改變了構(gòu)造結(jié)果的值左腔。
我在彈幕上問，為什么沒有做歸去來兮捅儒？覃超解釋說：
遞歸函數(shù)的參數(shù)本身就會進行歸去來兮的還原
也可以手動歸去來兮
如果是手動液样，中間變量就是全局共享的
否則是直接進行值拷貝又創(chuàng)建了一份
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可以避免重復(fù)創(chuàng)建對象。具體可以看這里：http://www.reibang.com/p/2c9e588def78
從前的版本
這個遞歸是不需要for循環(huán)的鞭莽，總結(jié)一下就是坊秸，從0開始構(gòu)造的遞歸是不需要for循環(huán)的。
另外想了很久為什么第一次打印((()))之后第二次會出棧4次澎怒，打印(()())褒搔，后來大概想明白了，因為前三次backtracking之后sb.deleteCharAt(sb.length() - 1);執(zhí)行完了就沒東西執(zhí)行了喷面，所以開始執(zhí)行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.reibang.com/p/2c9e588def78
