回溯算法（C/C++）

什么是回溯算法

?回溯法是一種選優(yōu)搜索法理疙，按選優(yōu)條件向前搜索霞势，以達(dá)到目標(biāo)烹植。但當(dāng)探索到某一步時(shí)，發(fā)現(xiàn)原先選擇并不優(yōu)或達(dá)不到目標(biāo)愕贡，就退回一步重新選擇草雕，這種走不通就退回再走的技術(shù)為回溯法，而滿足回溯條件的某個(gè)狀態(tài)的點(diǎn)稱為“回溯點(diǎn)”固以。許多復(fù)雜的墩虹，規(guī)模較大的問題都可以使用回溯法。
?回溯算法類似于枚舉的過程憨琳，當(dāng)搜索時(shí)遇到不滿足條件诫钓，回退到上一個(gè)，嘗試別的路徑篙螟。
?回溯是遞歸的產(chǎn)物菌湃，有遞歸一定有回溯。

回溯算法的效率

?回溯算法并不是什么高效的算法闲擦，因?yàn)楸举|(zhì)上時(shí)去遍歷所有元素慢味，找出所有可能场梆，然后選出需要的答案墅冷。那為什么還要回溯法，簡單來說或油，不是所有的問題都能用什么巧妙的方法來解決的寞忿，有些問題你能暴力求解出來就不錯(cuò)了。

回溯法能解決的問題

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

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

概念理解總結(jié)

?回溯法使用多了不難發(fā)現(xiàn)辖佣，回溯法的問題都可以抽象轉(zhuǎn)換為樹型結(jié)構(gòu)霹抛，你可以畫一棵樹來分析這類問題，因?yàn)榛厮莘ń鉀Q的都是在集合中遞歸查找子集卷谈，集合的大小就構(gòu)成了樹的寬度杯拐，遞歸的深度，都構(gòu)成的樹的深度。因?yàn)檫f歸就要有終止條件端逼，所以必然是一顆高度有限的樹（N叉樹）朗兵。

處理方法

針對(duì)所給問題，確定問題的解空間：首先應(yīng)明確定義問題的解空間顶滩，問題的解空間應(yīng)至少包含問題的一個(gè)（最優(yōu)）解余掖。
確定結(jié)點(diǎn)的擴(kuò)展搜索規(guī)則。
以深度優(yōu)先方式搜索解空間礁鲁，并在搜索過程中用剪枝函數(shù)避免無效搜索盐欺。

回溯算法模板框架

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

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

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

解決實(shí)際問題

$\color{red}{題：給定一個(gè)只包含數(shù)字的字符串着憨，復(fù)原它并返回所有可能的 IP 地址格式墩衙。}$
有效的 IP 地址正好由四個(gè)整數(shù)（每個(gè)整數(shù)位于 0 到 255 之間組成，且不能含有前導(dǎo) 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啊柱衔，我們?cè)囈幌禄厮莸姆椒ā?br> 1.首先確定參數(shù)
全局變量數(shù)組path存放切割后回文的子串樊破，二維數(shù)組result存放結(jié)果集。本題遞歸函數(shù)參數(shù)還需要startIndex唆铐，因?yàn)榍懈钸^的地方哲戚，不能重復(fù)切割，和組合問題也是保持一致的艾岂。如果是一個(gè)集合來求組合的話顺少，就需要startIndex，startIndex來控制for循環(huán)的起始位置王浴。

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

2.遞歸終止條件
本題明確要求只會(huì)分成4段，所以用分割的段數(shù)作為終止條件氓辣。pointNum表示點(diǎn)的數(shù)量秒裕，pointNum為3說明字符串分成了4段了。然后驗(yàn)證一下第四段是否合法钞啸，如果合法就加入到結(jié)果集里几蜻。

if (pointNum == 3) { // 逗點(diǎn)數(shù)量為3時(shí)癞松，分隔結(jié)束   
    // 判斷第四段子字符串是否合法，如果合法就放進(jìn)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]這個(gè)區(qū)間就是截取的子串入蛆，需要判斷這個(gè)子串是否合法响蓉。
如果合法就在字符串后面加上符號(hào).表示已經(jīng)分割。
如果不合法就結(jié)束本層循環(huán)哨毁，剪掉此分支枫甲。

然后就是遞歸和回溯的過程，遞歸調(diào)用時(shí)扼褪，下一層遞歸的startIndex要從i+2開始（因?yàn)樾枰谧址屑尤肓朔指舴?）想幻，同時(shí)記錄分割符的數(shù)量pointNum 要 +1』敖剑回溯的時(shí)候脏毯，就將剛剛加入的分隔符. 刪掉就可以了，pointNum也要-1幔崖。

class Solution {  
private:  
    vector<string> result;// 記錄結(jié)果  
    // startIndex: 搜索的起始位置食店，pointNum:添加逗點(diǎn)的數(shù)量  
    void backtracking(string& s, int startIndex, int pointNum) {  
        if (pointNum == 3) { // 逗點(diǎn)數(shù)量為3時(shí)，分隔結(jié)束  
            // 判斷第四段子字符串是否合法赏寇，如果合法就放進(jìn)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] 這個(gè)區(qū)間的子串是否合 法   
                s.insert(s.begin() + i + 1 , '.');  // 在i的后面插入一個(gè)逗點(diǎn)   
                pointNum++;  
                backtracking(s, i + 2, pointNum);   // 插入逗點(diǎn)之后下一個(gè)子串的起始位置為i+2  
                pointNum--;                         // 回溯   
                s.erase(s.begin() + i + 1);         // 回溯刪掉逗點(diǎn)    
            } else break; // 不合法吉嫩，直接結(jié)束本層循環(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.reibang.com/p/4abfd96d91e6