回溯算法（C/C++）

2020-11-07 本文已影响0人冀望的air

什么是回溯算法

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法。
回溯算法类似于枚举的过程，当搜索时遇到不满足条件，回退到上一个，尝试别的路径。
回溯是递归的产物，有递归一定有回溯。

回溯算法的效率

回溯算法并不是什么高效的算法，因为本质上时去遍历所有元素，找出所有可能，然后选出需要的答案。那为什么还要回溯法，简单来说，不是所有的问题都能用什么巧妙的方法来解决的，有些问题你能暴力求解出来就不错了。

回溯法能解决的问题

这里是综合了一下参考的别人写的，有这么几种情况适合回溯法解决：

组合问题：N个数里面按一定规则找出k个数的集合
排列问题：N个数按一定规则全排列，有几种排列方式
切割问题：一个字符串按一定规则有几种切割方式
子集问题：一个N个数的集合里有多少符合条件的子集
棋盘问题：N皇后，解数独等等

概念理解总结

回溯法使用多了不难发现，回溯法的问题都可以抽象转换为树型结构，你可以画一棵树来分析这类问题，因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度。因为递归就要有终止条件，所以必然是一颗高度有限的树（N叉树）。

处理方法

针对所给问题，确定问题的解空间：首先应明确定义问题的解空间，问题的解空间应至少包含问题的一个（最优）解。
确定结点的扩展搜索规则。
以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

回溯算法模板框架

void backtracking(参数) {  
    if (终止条件) {  
        存放结果;  
        return;  
    }  

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {  
        处理节点;  
        backtracking(路径，选择列表); // 递归  
        回溯，撤销处理结果  
    }  
}

for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历

解决实际问题

$\color{red}{题：给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。}$
有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。例如："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.首先确定参数
全局变量数组path存放切割后回文的子串，二维数组result存放结果集。本题递归函数参数还需要startIndex，因为切割过的地方，不能重复切割，和组合问题也是保持一致的。如果是一个集合来求组合的话，就需要startIndex，startIndex来控制for循环的起始位置。

 vector<string> result;// 记录结果  
    // startIndex: 搜索的起始位置，pointNum:添加逗点的数量    
    void backtracking(string& s, int startIndex, int pointNum) {

2.递归终止条件
本题明确要求只会分成4段，所以用分割的段数作为终止条件。pointNum表示点的数量，pointNum为3说明字符串分成了4段了。然后验证一下第四段是否合法，如果合法就加入到结果集里。

if (pointNum == 3) { // 逗点数量为3时，分隔结束   
    // 判断第四段子字符串是否合法，如果合法就放进result中  
    if (isValid(s, startIndex, s.size() - 1)) {  
        result.push_back(s);  
    }  
    return;  
}

3.单层搜索的逻辑
在for (int i = startIndex; i < s.size(); i++)循环中 [startIndex, i]这个区间就是截取的子串，需要判断这个子串是否合法。
如果合法就在字符串后面加上符号.表示已经分割。
如果不合法就结束本层循环，剪掉此分支。

然后就是递归和回溯的过程，递归调用时，下一层递归的startIndex要从i+2开始（因为需要在字符串中加入了分隔符.），同时记录分割符的数量pointNum 要 +1。回溯的时候，就将刚刚加入的分隔符. 删掉就可以了，pointNum也要-1。

class Solution {  
private:  
    vector<string> result;// 记录结果  
    // startIndex: 搜索的起始位置，pointNum:添加逗点的数量  
    void backtracking(string& s, int startIndex, int pointNum) {  
        if (pointNum == 3) { // 逗点数量为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] 这个区间的子串是否合 法   
                s.insert(s.begin() + i + 1 , '.');  // 在i的后面插入一个逗点   
                pointNum++;  
                backtracking(s, i + 2, pointNum);   // 插入逗点之后下一个子串的起始位置为i+2  
                pointNum--;                         // 回溯   
                s.erase(s.begin() + i + 1);         // 回溯删掉逗点    
            } else break; // 不合法，直接结束本层循环  
        }  
    }  
    // 判断字符串s在左闭又闭区间[start, end]所组成的数字是否合法  
    bool isValid(const string& s, int start, int end) {  
        if (start > end) {  
            return false;   
        }     
        if (s[start] == '0' && start != end) { // 0开头的数字不合法  
                return false;  
        }  
        int num = 0;  
        for (int i = start; i <= end; i++) {  
            if (s[i] > '9' || s[i] < '0') { // 遇到非数字字符不合法  
                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
https://www.jianshu.com/p/4abfd96d91e6