[数据结构与算法]leetcode 93. 复原 IP 地址 刷了一天，小白忘了整理回溯法了

强烈安利一名大佬：代码随想录链接如下

代码随想录

给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 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 地址。

```cpp
class Solution {
public:
    vector<string> result;
    vector<string> restoreIpAddresses(string s) {
        backstracking(s, 0, 0);
        return result;
    }
    void backstracking(string s, int index, int pointNum) {  //index代表切割的位置，pointNum代表已经使用的 . 的个数
        if(pointNum == 3) {
            if (isTrue(s, index, s.size() - 1)) {
                result.push_back(s);
            }
            return ;
        }
        for(int i = index; i < s.size(); i++) {
            if (!isTrue(s, index, i)) { 
                break;  //break用于完全结束一个循环这一块都不行，更别说别的了
            }
            //string str = s.substr(index, i);
            s.insert(s.begin() + i + 1, '.');   // 插入begin() + i + 1的点.
            pointNum++;                     
            backstracking(s, i + 2, pointNum); //由于已经插入 . ，所以下次循环在 i + 2 处开始了
            pointNum--;
            s.erase(s.begin() + i + 1);  //回溯法，删除begin() + i + 1的点

        }

    }
    bool isTrue(string s, int left, int right) {  // 判断截取的ip这一段是否有效
        if (left > right || ((right - left) > 2) ) {
            return false;
        }
        if (s[left] == '0' && left != right) {
            return false;
        }
        int sum = 0;
        for (int i = left; i <= right; i++) {
            if (s[i] > '9' || s[i] < '0') {
                return false;
            }
            int temp = s[i] - '0';
            sum = 10 * sum + temp;   //累加法
            if (sum > 255) {
                return false;
            }
        }
        return true;
    }
};