Given a string containing only digits, restore it by returning all possible valid IP address combinations.
For example:
Given “25525511135”,return [“255.255.11.135”, “255.255.111.35”]. (Order does not matter)
最開始看到這道題的時候也是毫無思路，囧啊。不過思考了一會兒，在紙上畫了一些圖示後發現可以按照這個思路求解。
這道題的主要思路是分治，將問題的規模不斷縮小。回溯中好多的題目都是使用這個思想來解題的。
IP地址被三個”.”分割成了4個部分，這裡我把每一個部分叫做一個段，依次為第0段，第1段，第2段，第3段。
那麼給定一個只包含數字的字符串，如果求出有效的ip地址呢？
以25525511135為例來分析。考慮第0段可能的取值，由於每一個段可以包含1位，2位或3位，那麼第0段可能的取值是：
2
25
255
第0段取值以後後面的字符串需要被分割成3段，那麼後面的字符能否被分割成3段呢？
第0段取上面的值後，剩余的部分依次為：
5525511135 ，字符串的長度為10，而3段最長也只能為9，所以第0段取2時沒有對應的有效ip地址。
525511135 ，這裡字符串的長度為9，即這個字符串還可能被分割成有效的3段。
25511135 ，這裡字符串的長度為8，即這個字符串還可能被分割成有效的3段。
然後再對525511135和25511135求分割成3段的方法。這裡問題規模就縮小了。需要被分割的段由4段變成了3了，字符串的長度也變短了。
遞歸退出的條件是遍歷到字符串尾端並且字符串被分割成了4段。
還需要注意的是:
如果一個段包含3個字符，那麼這三個字符不能大於”255”,這是ip地址的基本知識； 如果一個字符包括2個或3個字符，它的第一個字符不能為0。runtime:4ms
class Solution {
public:
vector restoreIpAddresses(string s) {
vector result;
string path;
helper(s,0,0,path,result);
return result;
}
void helper(string &s,int num,int pos,string &path,vector& result)
{
//遍歷完給定字符串，並且生成了個段時
if(pos==s.size()&&num==4)
{
//這裡需要去除掉path最後的.
result.push_back(path.substr(0,path.size()-1));
return;
}
//如果該段包含的字符數大於規定的最大數目，那麼直接退出，可以把這個判斷放在下面的if中，
//但是三個if都需要加，所以放在這兒更簡潔一些。
if(s.size()-pos>3*(4-num))
return;
//該段只含有一個字符
if(pos
另外幾道使用分治將問題規模縮小的使用回溯求解的題目：
LeetCode60:Permutation Sequence
LeetCode131:Palindrome Partitioning
LeetCode17:Letter Combinations of a Phone Number
