https://leetcode.cn/problems/restore-ip-addresses/description/

<aside> 💡

整体与131分割回文串类似，仅有部分不同：

1. 分割回文串时剪枝后是continue（当前子串不是回文串但右边界右移后还有可能是回文串，所以只剪当前i），本题剪枝后是break（当前子串不是IP整数，右边界不管怎么移动之后的子串都不可能是IP整数，所以剪掉整个startIndex）
2. 除了子串是否合法外还可根据字符串长度进行剪枝 </aside>

// 将路径数组转换为IP字符串
string pathToIP(vector<string> path) {
		string ip = "";
		for (int i = 0; i < path.size(); ++i) {
				if (i < path.size() - 1)
						ip += path[i] + '.';
				else
						ip += path[i];
		}
		return ip;
}

// 判断字符串是否是合法的IP整数
bool isIP(string s) {
		if (s.size() >= 2 && s[0] == '0')
				return false;
		else {
				int num = std::stoi(s);
				return num >= 0 && num <= 255;
		}
}

vector<string> ans;
vector<string> path;

void backtracking(int startIndex, string& s) {
		if (startIndex > s.size() - 1 && path.size() == 4) {
				ans.push_back(pathToIP(path));
				return;
		}
	
	  // 根据字符串长度进行剪枝：
		// startIndex与path.size间必须满足以下条件：4 - path.size() <= s.size - startIndex <= 3 * (4 - path.size())
		if (4 - path.size() > s.size() - startIndex || s.size() - startIndex > 3 * (4 - path.size()))
				return;
	
		for (int i = startIndex + 1; i <= s.size(); ++i) {
				string substr(s.begin() + startIndex, s.begin() + i);
				// 子串不是IP地址时进行剪枝（直接跳过当前startIndex）
				if (!isIP(substr))
						break;
				else {
						path.push_back(substr);
						backtracking(i, s);
						path.pop_back();
			}
		}
}

vector<string> restoreIpAddresses(string s) {
		backtracking(0, s);
		return ans;
}