字符串回溯算法题模板

这个模板适用于给出一个字符串，然后从字符串中判断其子字符串是否满足某一性质。
比如：
93. 复原IP地址
题目给出一个字符串，需要求出所有可能的 IP 地址格式。
131. 分割回文串
题目给出一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
306.累加数
累加数是一个字符串，组成它的数字可以形成累加序列。一个有效的累加序列必须至少包含 3 个数。除了最开始的两个数以外，字符串中的其他数都等于它之前两个数相加的和。

这个模板如下：

Class Solution{
	//res用来保存最后结果
	List<String> res = new ArrayList<>();
	//递归函数，list用于保存满足条件的结果，pos用于指示字符的位置，input为输入的字符串
	public void helper(List<String> list,int pos,String input){
		//当遍历到最后一个字符时，加入结果集
		if(pos == intput.length() && 其它的终止条件){
			res.add(new ArrayList<>(list));
			return;
		}
		for(int i = 1;i <= 子字符需要的长度;i++){
			//剪枝
			if (pos+ i > s.length()) break;
			//获得子字符串
			String subStr = input.subString(pos,pos+i);
			//根据题目要求筛选子字符串
			子字符串筛选....
			//将符合条件的子字符串加入list
			list.add(subStr);
			helper(list,pos+1,input);
			//回退
			list.remove(list.size()-1);
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

93. 复原IP地址

/**
 * ip地址每段在0~255之间，且不能以0作为开头，如012，这些可以作为剪枝条件
1