什么是回溯算法

?回溯法是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達到目標。但當探索到某一步時，發(fā)現(xiàn)原先選擇并不優(yōu)或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀態(tài)的點稱為“回溯點”。許多復雜的，規(guī)模較大的問題都可以使用回溯法。
?回溯算法類似于枚舉的過程，當搜索時遇到不滿足條件，回退到上一個，嘗試別的路徑。
?回溯是遞歸的產(chǎn)物，有遞歸一定有回溯。

回溯算法的效率

?回溯算法并不是什么高效的算法，因為本質上時去遍歷所有元素，找出所有可能，然后選出需要的答案。那為什么還要回溯法，簡單來說，不是所有的問題都能用什么巧妙的方法來解決的，有些問題你能暴力求解出來就不錯了。

回溯法能解決的問題

這里是綜合了一下參考的別人寫的，有這么幾種情況適合回溯法解決：

• 組合問題：N個數(shù)里面按一定規(guī)則找出k個數(shù)的集合
• 排列問題：N個數(shù)按一定規(guī)則全排列，有幾種排列方式
• 切割問題：一個字符串按一定規(guī)則有幾種切割方式
• 子集問題：一個N個數(shù)的集合里有多少符合條件的子集
• 棋盤問題：N皇后，解數(shù)獨等等

概念理解總結

?回溯法使用多了不難發(fā)現(xiàn)，回溯法的問題都可以抽象轉換為樹型結構，你可以畫一棵樹來分析這類問題，因為回溯法解決的都是在集合中遞歸查找子集，集合的大小就構成了樹的寬度，遞歸的深度，都構成的樹的深度。因為遞歸就要有終止條件，所以必然是一顆高度有限的樹（N叉樹）。

處理方法

• 針對所給問題，確定問題的解空間：首先應明確定義問題的解空間，問題的解空間應至少包含問題的一個（最優(yōu)）解。
• 確定結點的擴展搜索規(guī)則。
• 以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。

回溯算法模板框架

void backtracking(參數(shù)) {  
    if (終止條件) {  
        存放結果;  
        return;  
    }  

    for (選擇：本層集合中元素（樹中節(jié)點孩子的數(shù)量就是集合的大小）) {  
        處理節(jié)點;  
        backtracking(路徑，選擇列表); // 遞歸  
        回溯，撤銷處理結果  
    }  
}  

for循環(huán)可以理解是橫向遍歷，backtracking（遞歸）就是縱向遍歷

解決實際問題

有效的 IP 地址 正好由四個整數(shù)（每個整數(shù)位于 0 到 255 之間組成，且不能含有前導 0），整數(shù)之間用 '.' 分隔。例如："0.1.2.201" 和 "192.168.1.1" 是 有效的 IP 地址，但是"0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 無效的 IP 地址。
問題想到用for可以解，但是這要多少層for啊，我們試一下回溯的方法。
1.首先確定參數(shù)
全局變量數(shù)組path存放切割后回文的子串，二維數(shù)組result存放結果集。本題遞歸函數(shù)參數(shù)還需要startIndex，因為切割過的地方，不能重復切割，和組合問題也是保持一致的。如果是一個集合來求組合的話，就需要startIndex，startIndex來控制for循環(huán)的起始位置。

 vector<string> result;// 記錄結果  
    // startIndex: 搜索的起始位置，pointNum:添加逗點的數(shù)量    
    void backtracking(string& s, int startIndex, int pointNum) {      

2.遞歸終止條件
本題明確要求只會分成4段，所以用分割的段數(shù)作為終止條件。pointNum表示點的數(shù)量，pointNum為3說明字符串分成了4段了。然后驗證一下第四段是否合法，如果合法就加入到結果集里。

if (pointNum == 3) { // 逗點數(shù)量為3時，分隔結束   
    // 判斷第四段子字符串是否合法，如果合法就放進result中  
    if (isValid(s, startIndex, s.size() - 1)) {  
        result.push_back(s);  
    }  
    return;  
}  

3.單層搜索的邏輯
在for (int i = startIndex; i < s.size(); i++)循環(huán)中 [startIndex, i]這個區(qū)間就是截取的子串，需要判斷這個子串是否合法。
如果合法就在字符串后面加上符號.表示已經(jīng)分割。
如果不合法就結束本層循環(huán)，剪掉此分支。

然后就是遞歸和回溯的過程，遞歸調用時，下一層遞歸的startIndex要從i+2開始（因為需要在字符串中加入了分隔符.），同時記錄分割符的數(shù)量pointNum 要 +1。回溯的時候，就將剛剛加入的分隔符. 刪掉就可以了，pointNum也要-1。

class Solution {  
private:  
    vector<string> result;// 記錄結果  
    // startIndex: 搜索的起始位置，pointNum:添加逗點的數(shù)量  
    void backtracking(string& s, int startIndex, int pointNum) {  
        if (pointNum == 3) { // 逗點數(shù)量為3時，分隔結束  
            // 判斷第四段子字符串是否合法，如果合法就放進result中  
            if (isValid(s, startIndex, s.size() - 1)) {  
                result.push_back(s);  
            }  
            return;  
        }    
        for (int i = startIndex; i < s.size(); i++) {   
            if (isValid(s, startIndex, i)) { // 判斷 [startIndex,i] 這個區(qū)間的子串是否合 法   
                s.insert(s.begin() + i + 1 , '.');  // 在i的后面插入一個逗點   
                pointNum++;  
                backtracking(s, i + 2, pointNum);   // 插入逗點之后下一個子串的起始位置為i+2  
                pointNum--;                         // 回溯   
                s.erase(s.begin() + i + 1);         // 回溯刪掉逗點    
            } else break; // 不合法，直接結束本層循環(huán)  
        }  
    }  
    // 判斷字符串s在左閉又閉區(qū)間[start, end]所組成的數(shù)字是否合法  
    bool isValid(const string& s, int start, int end) {  
        if (start > end) {  
            return false;   
        }     
        if (s[start] == '0' && start != end) { // 0開頭的數(shù)字不合法  
                return false;  
        }  
        int num = 0;  
        for (int i = start; i <= end; i++) {  
            if (s[i] > '9' || s[i] < '0') { // 遇到非數(shù)字字符不合法  
                return false;  
            }  
            num = num * 10 + (s[i] - '0');  
            if (num > 255) { // 如果大于255了不合法  
                return false;   
            }   
        }  
        return true;    
    }  
public:
    vector<string> restoreIpAddresses(string s) {  
        result.clear();  
        backtracking(s, 0, 0);  
        return result;  
    }  
};  

文章參考：https://mp.weixin.qq.com/s/gjSgJbNbd1eAA5WkA-HeWw
https://mp.weixin.qq.com/s/v--VmA8tp9vs4bXCqHhBuA
http://www.itdecent.cn/p/4abfd96d91e6