（回溯分割）leetcode93 复原IP地址

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
//卡尔的图不是按照程序执行过程而是直接画程序会执行的过程
// 实际执行是：n个字符，递推n+1后（叶子节点），回溯n层执行循环i++（n层的index不变），再递推到n+1的叶子结点，n层的循环执行完后再到n-1层的循环体i++，接着递推到n层（回溯看成左右中序遍历，遍历完叶子结点）//看卡尔的最终画的图也要听边画边讲	
//切割的竖线就是当前层的index，也就是当前层的i的值，切割的基础是组合
//index在组合和分割中处于本层的起始值
//本题重心放在在str里插入'.'，ip地址是否为需要的，看c==3最后一个点之后的IP地址值是否合法，同时判断两点间的值是否合法//ip地址数字长度应该为0-12之间
//根据断点调试的规律发现，上一个点的后面是index的值，最后一个点的位置是i的后面。********
// c==3 到n+1层时 index等于最后一个点
//小功能整合，各司其职
vector<string>ans;
bool check(string str,int left,int right)
{if (left > right)return false;if (str[left] == '0' && left<right)//这里是判断元素是否为0而不是下标,排除前导，考虑到left和right相等且均为0符合条件（127.0.0.1）return false;int sum = 0;int j = 1;for (int i = right;i >= left;i--){sum += (str.at(i) - 48) * j;j *= 10;}if (sum > 255 || sum < 0) //这里要用或而不是并，不存在即大于255又小于0的数return false;return true;
}void backtracking(string &str,int index,int c)
{if (c==3){if(check(str,index,str.size()-1))ans.push_back(str);return;}for (int i = index;i < str.size();i++){if (check(str, index, i)){str.insert(i + 1, ".");//25525511135 ---1.1135最后1135不符合标准。11.135符合标准。111.35符合标准。1113后不插入点,i+2=s.size()，结束循环和程序，回溯++c;}elsereturn;backtracking(str, i + 2, c);str.erase(i+1, 1);--c;}}int main()
{int c=0;string str = "101023";backtracking(str, 0,c);for (auto &n : ans){cout << n << endl;}return 0;
}

断点调试真是个好东西，断多行