當(dāng)一個dfs在for循環(huán)里陨仅，那么for循環(huán)的初始值寫成i = start的時候彤路，通常是想讓遞歸在進(jìn)入下一層的時候不從原來的位置開始（例如combination sum ii）。
但當(dāng)我做到Palindrome Partitioning這題的時候惫恼，才發(fā)現(xiàn)start原來也是會增加的棚贾；因為通常start都只是用來標(biāo)記i酥宴，但這題start本身也參與到了每次的dfs里纲辽。
isPalindrome(s, start, i)
這樣一下子增大了很多思維難度颜武。。
于是我又調(diào)試了一下拖吼，發(fā)現(xiàn)對于"aab"鳞上，dfs執(zhí)行順序大概是這樣的：
start , i
0, 0
1, 1
2, 2 add to result
1, 1
1, 2
0, 0
0, 1
2, 2 add to result
0, 1
0, 2
所以，答案是這種：
[a, a, b], [aa, b]
這題我其實還是有點無法想象遞歸過程的吊档，我能想到就是一個類似右上三角矩陣那么執(zhí)行下去篙议，對于終止條件 if (start == s.length()) ，我知道i會從start到s.length這么刷（被for控制著）籍铁，但有點想不通為什么start會往復(fù)地從頭到尾這么刷涡上。但要明白，start會多次從0到尾刷拒名，而不是只執(zhí)行一次 。
再次理解04282017
早上又稍微想了一下芋酌，既然前三次遞歸start會從0到1再到2增显，也就說明i一定會start開始從0走到最后和從1，2走到最后。如此就往復(fù)多次了同云。
不必想糖权，不必想。炸站。
中午吃完飯的間隙寫了一下這題的代碼星澳，是按照之前看過答案的印象里寫的。調(diào)試了2次旱易，AC了禁偎。
public class Solution {
public List<List<String>> partition(String s) {
List<List<String>> list = new ArrayList<>();
backtrack(list, new ArrayList<String>(), s, 0);
return list;
}
public void backtrack(List<List<String>> list, List<String> tempList, String s, int start) {
if (start == s.length()) {
list.add(new ArrayList<String>(tempList));
return;
}
for (int i = start; i < s.length(); i++) {
if (isPalindrome(s , start, i)) {
tempList.add(s.substring(start, i + 1));
backtrack(list, tempList, s, i + 1);
tempList.remove(tempList.size() - 1);
}
}
}
private boolean isPalindrome(String s, int low, int high) {
while (low <= high) {
if (s.charAt(low++) != s.charAt(high--)) return false;
}
return true;
}
}
調(diào)試的第一次是，low<high改成了low<=high阀坏。
第二次是如暖，if (isPalindrome(s , start, i)) 的判斷，之前寫成sPalindrome(s.substring(start , i+1) , start, i)了忌堂。
