資訊專欄INFORMATION COLUMN
摘要：什么是回溯算法回溯法是一種系統搜索問題解空間的方法。解空間定義為與數字長度相同。最后，為什么要掌握回溯法因為懂了回溯法之后筆試里的很多題就算不了，起碼成功運行到之間是沒問題的。
什么是回溯算法？
回溯法是一種系統搜索問題解空間的方法。為了實現回溯，需要給問題定義一個解空間。
說到底它是一種搜索算法。只是這里的搜索是在一個叫做解空間的地方搜索。
而往往所謂的dfs，bfs都是在圖或者樹這種數據結構上的搜索。
根據定義來看，要實現回溯，需要兩點1搜索，2解空間
先看什么是解空間。
就是形如數組的一個向量[a1,a2,....,an]。這個向量的每個元素都是問題的部分解，只有當這個數組的每一個元素都填滿(得到全部解)的時候，才表明這個問題得到了解答。
再看搜索。
最簡單的就是for循環，上面的向量有n個維度，因此就是n個for循環。
形如：
for(求a1位置上的解)
for(求a2位置上的解)
for(求a3位置上的解)
......
......
for(求an位置上的解)
但是如果n是100？n是100000？那么如何回溯？
當然也可以寫n個for循環，但是這樣的程序會慘不忍睹。。。而且似乎10000個(不過往往回溯的時間復雜度太大，一般n不會這么大)for循環也很難寫出來。。。
因此我們需要一種全新的書寫回溯的方法。形如：
void backtrack(int i,int n,other parameters)
{
if( i == n)
{
//get one answer
record answer;
return;
}
//下面的意思是求解空間第i個位置上的下一個解
for(next ans in position i of solution space)
{
backtrack(i+1,n,other parameters);
}
}
就是這么簡單！！！
上面的模板適用于所有"解空間確定"的回溯法的問題！！！
上面的i代表解空間的第i個位置，往往從0開始，而n則代表解空間的大小。每一次的backtrack(i,n,other)調用,代表求解空間第i個位置上的解。而當i=n時，代表解空間上的所有位置的解都已經求出。
有了上述模板，我們就解決了搜索的問題。
因此幾乎所有回溯的問題的難度都在于如何定義解空間。
下面通過題目，帶入模板，然后再看我的解答，來感知一下如何定義解空間。
全排列https://segmentfault.com/a/11...
即對沒有重復數字的數組a=[a1,a2,a3,...an]求全排列。
解空間定義為s=[s1,s2,s3,....sn]與數字長度相同。s的每一個元素s【i】(i >= 0&&i < n),都為數組a中的任意元素a【j】(j >= 0&&j < n)，不過要保證任意的s【i】不相等。
這里唯一復雜的地方是需要用一個boolean【】數組來表明哪些數已經用過，這樣才能保證任意的s【i】不相等。
因此我們看到，回溯本身是很簡單的，單純的模板套用，難的在于需要根據回溯條件來定義各種別的變量，以及最后結果的記錄。
探測路徑https://leetcode-cn.com/probl... (這個下面給出ac 代碼)
這個題很難，但是掌握了如何定義解空間之后再做這個題就會感覺是小兒科了。
這里的解空間s = [s1,s2,s3,....sn]中的每一個元素s【i】代表格子的坐標(x,y),因此從邏輯上來看，s應該是一個類類型的數組。不過，這個題求的是數目，而不是最后的確切路徑，因此解空間在這里并沒有記錄。
java ac代碼：
class Solution {
int ans;
public int uniquePathsIII(int[][] grid) {
if(grid.length == 0)return 0;
int num = 0;
int x = 0,y = 0;
for(int i = 0;i < grid.length;i++)
for(int j = 0;j < grid[0].length;j++){
if(grid[i][j] == 1||grid[i][j] == 0)num++;
if(grid[i][j] == 1){x = i;y = j;}
}
backtrack(0,num,x,y,grid,new boolean[grid.length][grid[0].length]);
return ans;
}
void backtrack(int i,int n,int x,int y,int[][]grid,boolean[][]flag)
{
if(!(x >= 0 && x < grid.length && y >= 0 && y < grid[0].length)||flag[x][y]||grid[x][y] == -1)
return;
if(i == n && grid[x][y] == 2)
{
ans++;
return;
}
flag[x][y] = true;
backtrack(i+1,n,x+1,y,grid,flag);
backtrack(i+1,n,x-1,y,grid,flag);
backtrack(i+1,n,x,y+1,grid,flag);
backtrack(i+1,n,x,y-1,grid,flag);
flag[x][y] = false;
}
}
上面這個題的解空間應該有N+1維才對，但是為了方便書寫，我只求出前n維位置的解，然后保證最后一維中位置是終點即可。
如果仍然覺得抽象，那么我建議大家把回溯想象成“填格子”游戲。
到leetcode上找回溯的專題，對于每一個回溯法可解的問題，看看這題需要填的格子(格子就是解空間)是什么。
比如n個不重復字母的全排列，不就是填充n個格子，填滿并且合法就得到一個解。
再比如在字母矩陣中搜索某個字符串比如"adrsad",那么格子有幾維？不就是填充維度是n的格子(字符串s長度n)，并且格子的第i(i從0開始到n-1)個維度上必須填s[i]，否則都是不合法的。用這種思路再做這個題看看會不會好做很多。
再比如括號生成，這里的格子的數量是括號對數乘以2，格子上填的就是左括號或者右括號，這里的剪枝條件是，當前右括號數量超過了左括號，或左括號數量超過了一半。當然為了剪枝需要在函數參數中維護左右括號數這兩個變量。
最后，為什么要掌握回溯法？？？
因為懂了回溯法之后筆試里的很多題就算AC不了，起碼成功運行70%到90%之間是沒問題的。
而且如果筆試題里有的數據集設計的不夠好，那么回溯甚至可以比動態規劃運行的還快。
而這對于獲得面試機會已經足夠了！！！
并且回溯很優美，很容易理解，因為說到底它不過就是個填格子的游戲罷了。
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/73446.html
摘要：輸入輸出分析題目由于我們需要找到多個組合，簡單的使用循環肯定是不行的，這時候我們可以使用回溯算法來解決這個問題。用回溯算法解決問題的一般步驟針對所給問題，定義問題的解空間，它至少包含問題的一個最優解。 題目描述 Given a set of candidate numbers (candidates) (without duplicates) and a target number ...
摘要：回溯算法在算法過程中就是類似于枚舉算法，嘗試在搜索過程中找到問題的解。 回溯算法( BackTrack )在算法過程中就是類似于枚舉算法，嘗試在搜索過程中找到問題的解。 使用回溯算法解題的一般步驟 使用回溯算法解題的一般步驟： 針對所給問題得出一般的解空間 用回溯搜索方法搜索解空間 使用深度優先去搜索所有解并包含適當的剪枝操作 LeetCode 使用回溯算法的題目主要有 36 題，...
摘要：用來存放每一個可能的結果最終結果深度優先遍歷剪枝當遍歷到底個數是，如果的元素個數剩余元素個數時，就不滿足條件了中元素個數達到，表示深度優先遍歷到達最深處了。 ?77. 組合77. 組合77. 組合 給定兩個整數?n?和?k，返回范圍?[1, n]?中所有可能的?k?個數的組合。 你可以按?任...
摘要：例如題目解析題目的意思很明顯，就是把兩個數字加起來，需要考慮進位的情況。總結這個題目如果都能獨立完成，那么水平已經可以足以應付國內各大企業的算法面。 歡迎大家前往騰訊云+社區，獲取更多騰訊海量技術實踐干貨哦~ 本文由落影發表 前言 LeetCode上的題目是大公司面試常見的算法題，今天的目標是拿下5道算法題： 題目1是基于鏈表的大數加法，既考察基本數據結構的了解，又考察在處理加法過程中...
閱讀 2415·2021-09-01 10:41
閱讀 1440·2019-08-30 14:12
閱讀 507·2019-08-29 12:32
閱讀 2856·2019-08-29 12:25
閱讀 2934·2019-08-28 18:30
閱讀 1704·2019-08-26 11:47
閱讀 973·2019-08-26 10:35
閱讀 2588·2019-08-23 18:06
