Jun 23 更新
昨天看sudoku solver又陷入強烈的疑惑中，為什么所有人的dfs函數(shù)都是boolean的返回值？？
今天回顧了一下之前知乎的回答，怎么讓N QUEENS在找到一個解后就跳出循環(huán)？其實之前理解得不夠深。今天又仔細跟了一下，發(fā)現(xiàn)：
情形一：void返回值
- ** 一次return只能跳出一層遞歸。**
下面的圖，為什么4 QUEENS的情形第一次是在第二層就停止，不會進入第三層？因為，在進入第三層之前調(diào)用了四次checkValid()發(fā)現(xiàn)第三層都不滿足，然后就會繼續(xù)往下走了，也就是走出for循環(huán)，程序結(jié)束，也就是隱含的return void，回到上一層繼續(xù)for循環(huán)。只跳出了一層遞歸。 - 找到一個解{1, 3, 0, 2}之后，加到解集里面去，然后return，會發(fā)生什么？
if (checkValid(row, col)) {
dfs(result, row + 1, n, col);
}
row 原本等于4了，但回來之后回到進去下一層之前的狀態(tài)，row = 3，再次for循環(huán)，不滿足， col: {1, 3, 0, 3}。
這時候，函數(shù)執(zhí)行完了，相當于return到上一層，row = 2。
繼續(xù)for循環(huán)發(fā)現(xiàn)，row = 2的后三個位置也不行了，又執(zhí)行完了，return的上一層，row = 1。
row = 1的i本來就在第四個位置了，回到上一層，row = 0.
那因為row = 0 的時候我們checkValid一定是true，所以就進入下一層DFS，row = 1。這時候會觸發(fā)我們加的
if (result.size() > 0) return;回到上一層。剛才i是等于2的，這時候就繼續(xù)吧，i = 3。然后往復進入下一層再回來，i = 4，也就是說在它進入row = 1的for循環(huán)之前讓它回到row = 1。那i = 4函數(shù)就執(zhí)行完了。這已經(jīng)是最頂層的夢了，也就真的醒來了。
也就是說，只有在回溯到了第一層，有機會進入下一層的時候才能讓它一步步return，不然它又往第二層第三層去找了。
這種方法對應的是把if (result.size() > 0) return;加到if (row == n) {
...
result.add(new ArrayList<String>(cell));
return;
}
后面的情況，所以還要再找一遍234層，最后回到第一層的時候，col變成了{1,3,3,3}，最后在從1層下到2層的時候才能一步步return，那優(yōu)化一下，把這個return放到for循環(huán)里面：
for (int i = 0; i < n; i++) {
if (result.size() > 0)
return;
col[row] = i;
if (checkValid(row, col)) {
dfs(result, row + 1, n, col);
}
}
這樣的話在backtracking的時候就不會再找1303這樣的數(shù)了，在{1,3,0,2}的狀態(tài)下就return了（也就是說都不用全局變量保存了，直接讀取這個數(shù)組的內(nèi)容就行了）。
情形二（重點）：boolean 遞歸中的if(dfs()){ return true;}的意義
剛才我又看了一遍，boolean類型的dfs函數(shù)真正的意義，其實是..
public boolean dfs(List<List<String>> result, int row, int n, int[] col) {
if (row == n) {
//保存解到解集
//...
return true;
}
for (int i = 0; i < n; i++) {
col[row] = i;
if (checkValid(row, col)) {
if (dfs(result, row + 1, n, col)) return true;
}
}
return false;
}
這時候如果找到一個解，return true的話，回到了上一層，上一層的入口的返回值也就成了true，這時候連for循環(huán)都不用走，直接就一層層退出了?。?！
這里的也不一定是boolean，用某個int值也行。
對于sudoku solver：
sudoku solver那題題目說，You may assume that there will be only one unique solution. 那我如果不及時讓他停下，他必然會找到解后又繼續(xù)找，最后回到原始狀態(tài)(為什么是最原始的狀態(tài)呢)。
那我能想到讓它變成void的方法就是找到一個解后保存下來，然后隨他去吧，恢復了也無所謂；當然也可以在for循環(huán)第一句里寫上：if (res != null) return; 但是這題不是要return一個結(jié)果，而是直接對傳進來的board進行操作，但我最后把board賦值回res，發(fā)現(xiàn)不行，就先不搞了。
1:11 AM 24/06/2017
原po：
上面這張圖是我思考的全排列類型DFS的運行過程，這種DFS的特點就是for循環(huán)里面有遞歸，舉個N Queens的例子：
for (int i = 0; i < n; i++) {
//i表示Q所在的列 從頭到尾遍歷一遍
col[row] = i;
if (checkValid(row, col)) {
dfs(result, row + 1, n, col);
}
}
一開始理解這種題的時候我完全不懂，現(xiàn)在懂一些了。原因就是這道N QueensII，因為這道題求解的是Queens的個數(shù)，我就在想，這個遞歸是找到一個答案就結(jié)束還是找到所有答案再結(jié)束呢？因為終止條件是row == n的時候return，但是return了之后recursion并沒有結(jié)束，因為經(jīng)過了for循環(huán)。如圖，其實對于每一個row，for循環(huán)都要從1到n-1走一遍，如果valid就進行到下一層的dfs里去，那么:
什么時候會backtracking(回溯)？
- 找到第一個解之后return的時候會backtracking。
第一張圖里的row==1的時候，Q在第三格發(fā)現(xiàn)后面checkVaild都失效了，就移動到第四格；然后走走走，到第二張圖的情形row == n找到一個解return的時候，這時候row回到row - 1的狀態(tài)，也就是上一層的夢境（第二張圖），彼時i = 2，那么i這時候繼續(xù)走，i= 3 了，checkValid失效，這時候遇到第二種： - row = 3的for循環(huán)走完了的時候。
這時候發(fā)現(xiàn)棧中還有上一層的遞歸沒有執(zhí)行完，上一層的夢醒了，繼續(xù)做。也就是把row =2的Q移動到第二個格子。
感謝盜夢空間。
怎么判斷是什么時候回溯？用IDE調(diào)試著看。
我還有個問題，怎么讓NQUEENS找到一個解就停止？
關(guān)于怎么讓NQUEENS找到一個解就停止，我在斗魚上提問了，覃超立刻回應了，就是加個終止條件。我加了這么一句就可以了：
if (result.size()>0) return;
對應于上面的圖二，就是每次回到上一層的夢，就發(fā)現(xiàn)這一層已經(jīng)不滿足了，所以一直回到第一層的夢，最后醒來。
參數(shù)「歸去來兮」的問題
也就是還原，恢復現(xiàn)場。這題的debug：
就在圖中這一步之前，col一直是[1,3,0,2]的狀態(tài)，沒有因為return就回到之前的[1,3,0,0]的狀態(tài)。但這題很特殊，因為第四個格子的數(shù)字2反正會被覆蓋所以不用還原。
我終于理解了??！intellij idea的左下角顯示的是函數(shù)棧
一直以來我不太理解什么時候歸去來兮，現(xiàn)在終于好像開竅了 。上面這題是Generate Paratheses的遞歸，我觀察到IDEA的左下角，竟然有9個dfs函數(shù)，按照9~1排列，點開之后，我發(fā)現(xiàn)右邊的variables grid里顯示的是每一個dfs的狀態(tài)！太神奇了。。哈哈，這里面的StringBuilder就不斷地在變化，第1個是""，第9個就是圖中的"(((())))"。
然后，找到一個解之后return的時候，回到dfs stack 8，結(jié)果8執(zhí)行完了沒有執(zhí)行stack7而是直接執(zhí)行了stack4，sb變成了"((("，然后執(zhí)行5，變成"((()"。這時候遞歸已經(jīng)不太好理解了，大概就是因為left對應著多個right，才導致left4的4個right執(zhí)行完了就開始執(zhí)行l(wèi)eft3的right們。我就不去深究了。重要的事，這里為什么不需要還原sb的問題，如果寫成：
if (right < left) {
sb.append((")"));
dfs(left, right + 1, result, sb, n);
sb.deleteCharAt(sb.length() - 1);
}
這樣是要還原的，因為這里sb沒有被當做參數(shù)傳到下一層遞歸里面去，只是sb的指針（也就是內(nèi)存地址）傳到dfs下一層去了，所以要手動還原，同樣的道理，52題的N-QUEENSII也是這樣，左邊的棧中我們會看到每個棧的col里面都是一樣的值，這是因為col沒有在參數(shù)中被改變，而是作為一個「全局」變量在使用，內(nèi)存地址沒有改變。
而Generate Parentheses這題就不一樣，回到上一層的夢境的時候，sb已經(jīng)回到之前的狀態(tài)了。
覃超對于word search那道題不需要還原的解釋：
參數(shù)的時候不要歸去來兮 值拷貝的
drunkpiano 22:48:46
定義在參數(shù)里面，并且參數(shù)做了值拷貝，就幫你還原了
drunkpiano 22:49:01
傳遞到board里面 只是把指針傳進去了 所以要手動還原
drunkpiano 22:49:14
currentWord值拷貝了，不用手動還原
再來理解一下，為什么對于遞歸參數(shù)中的i,j這些index的值不需要還原，因為它們是基本數(shù)據(jù)類型啊，本身就沒有引用，也就是說，只有在遞歸的參數(shù)是指向原來的某個引用的指針的時候，才需要還原。
這也是覃超為什么說Generate Parentheses 那題用StringBuilder雖然需要恢復現(xiàn)場，但好處是不會每次都創(chuàng)建新的對象。
今天弄懂了這些還是挺開心的。感覺對dfs的理解加深了不少。想起MK書里寫的，你做得不好不代表你不能做啊。。做得慢不代表你不會做啊。。慢慢來吧。
對了，差點忘了貼一下我盲寫的這題的AC代碼,注意checkValid那邊。
public class Solution {
int num = 0;
public int totalNQueens(int n) {
int[] col = new int[n];
dfsHelper(n, col, 0);
return num;
}
private void dfsHelper(int n, int[] col, int row) {
if (row == n) {
num++;
return;
}
for (int i = 0; i < n; i++) {
col[row] = i;
if (checkValid(row, col)) {
dfsHelper(n, col, row + 1);
}
}
}
private boolean checkValid(int row, int[] col) {
for (int i = 0; i < row; i++)
// for (int j = i + 1; j < row; j++) {
//不要用double for cycle，因為row之前的已經(jīng)valid了不需要比對了，只需要把每個i跟row比
if (Math.abs(i - row) == Math.abs(col[i] - col[row]) || col[i] == col[row]) {
return false;
// }
}
return true;
}
}
