Jun 23 更新
昨天看sudoku solver又陷入強烈的疑惑中键俱，為什么所有人的dfs函數(shù)都是boolean的返回值兰绣？？
今天回顧了一下之前知乎的回答编振，怎么讓N QUEENS在找到一個解后就跳出循環(huán)缀辩？其實之前理解得不夠深。今天又仔細跟了一下踪央，發(fā)現(xiàn)：
情形一：void返回值
- ** 一次return只能跳出一層遞歸臀玄。**
下面的圖，為什么4 QUEENS的情形第一次是在第二層就停止畅蹂，不會進入第三層健无？因為，在進入第三層之前調用了四次checkValid()發(fā)現(xiàn)第三層都不滿足液斜，然后就會繼續(xù)往下走了累贤，也就是走出for循環(huán)，程序結束少漆，也就是隱含的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í)行完了。這已經是最頂層的夢了捉蚤，也就真的醒來了抬驴。
也就是說，只有在回溯到了第一層缆巧，有機會進入下一層的時候才能讓它一步步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ù)組的內容就行了）推捐。
情形二（重點）：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一個結果膀篮，而是直接對傳進來的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ù)燎潮，我就在想，這個遞歸是找到一個答案就結束還是找到所有答案再結束呢扼倘？因為終止條件是row == n的時候return确封，但是return了之后recursion并沒有結束除呵，因為經過了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調試著看龄恋。
我還有個問題，怎么讓NQUEENS找到一個解就停止凶伙？
關于怎么讓NQUEENS找到一個解就停止郭毕，我在斗魚上提問了，覃超立刻回應了函荣，就是加個終止條件显押。我加了這么一句就可以了：
if (result.size()>0) return;
對應于上面的圖二，就是每次回到上一層的夢傻挂，就發(fā)現(xiàn)這一層已經不滿足了乘碑，所以一直回到第一層的夢，最后醒來金拒。
參數(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在张，結果8執(zhí)行完了沒有執(zhí)行stack7而是直接執(zhí)行了stack4，sb變成了"((("矮慕，然后執(zhí)行5帮匾，變成"((()"。這時候遞歸已經不太好理解了痴鳄，大概就是因為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的指針（也就是內存地址）傳到dfs下一層去了，所以要手動還原猫态，同樣的道理佣蓉，52題的N-QUEENSII也是這樣披摄，左邊的棧中我們會看到每個棧的col里面都是一樣的值，這是因為col沒有在參數(shù)中被改變勇凭，而是作為一個「全局」變量在使用疚膊，內存地址沒有改變。
而Generate Parentheses這題就不一樣虾标，回到上一層的夢境的時候寓盗，sb已經回到之前的狀態(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ù)據類型啊，本身就沒有引用库继，也就是說箩艺，只有在遞歸的參數(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之前的已經valid了不需要比對了嫁佳，只需要把每個i跟row比
if (Math.abs(i - row) == Math.abs(col[i] - col[row]) || col[i] == col[row]) {
return false;
// }
}
return true;
}
}
