因為自己在學習回溯算法的時候一直不清楚回溯的具體過程， 可能是因為自己太笨，這個問題困擾了我好幾天。回溯還是挺有用的，樹的遍歷，全排列問題都可以用回溯算法解。面試的時候好像也比較側重回溯算法和動態規劃。

回溯形象解釋下：假設你要從你家去你女朋友家，沒有導航，但是她告訴你了，從你家到她家要只需經過兩個十字路口就可以，這個時候怎么辦呢，只能是從第一個十字路口選擇一個方向（A）然后一直走遇到第二個十字路口，然后你又隨便選擇了一個方向（a）走，過了一會你打電話告訴女朋友你走的那條路周圍的環境，然后你女友告訴你：死鬼那條路不對，這個時候，只能回到第二個十字路口那選擇(b，c，d)方向，不幸的是你一開始就選擇錯了十字路口，四條路試完，只能回到第一個十字路口，再次選擇，最后，你把第一個十字路口的四個方向都試完，你一定能到女友家，然后一頓云雨，正當你大汗淋淋的時候戛然而止，你說：媽的，我還有一道回溯算法的題沒做，回去做了。卒

玩笑歸玩笑，拿個具體的例子說明一下。

這道題來源于leetcode

class Solution { public:vector<vector<int>> subsets(vector<int>& nums) {vector<vector<int> > res;vector<int> tmp;helper(res,tmp,nums,0);return res;}void helper(vector<vector<int> >& res,vector<int> &tmp,vector<int>& nums,int level){if(tmp.size()<=nums.size()){res.push_back(tmp);}for(int i=level;i<nums.size();i++){tmp.push_back(nums[i]);helper(res,tmp,nums,i+1);}tmp.pop_back();} };

注：tmp一開始為[] ，在后面寫的時候不再說寫入tmp和res。

a)：i=0 開始 遞歸回溯 ，此時tmp里面有[1] 進入helper后 res里面有 [1]?

b）i+1 變為1 注意這個i+1并不是for循環里面的i++,而是你遞歸里面的i+1。這是理解回溯算法的關鍵，因為不是for循環里面的i+1，所以for循環里面還有i=1,i=2沒用，相當于十字路口的其他方向，回溯是回到這里，tmp變為[1,2],res里面有[1][1,2]。

c)i+1 tmp：[1,2,3];res:[1][1,2][1,2,3];此時發現i=4不滿足for循環的條件，執行tmp.pop_back（）tmp為空。這個時候要回溯了，因為已經走到路的盡頭了，回到最近的那個地方也就是b）,此時我們發現2那個方向已經走過了所以不再走，換另一個方向，即for循環中的i+1。也就是說tmp不再插入2了，插入3變為[1,3]。然后又滿足for循環了，執行tmp.pop_back（）tmp為空。此時? b)試完了，一共兩個方向，即i=1和i=2.然后回到? a) tmp :[2] res:[1][1,2][1,2,3],[1,3] [2]。以此類推，應該是可以明白了，到這里。

?

?

總結

以上是生活随笔為你收集整理的回溯算法超详细讲解（附代码）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。