（回溯分割）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;
			}
			else
			return;
				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;
}

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