93.复原IP地址
思路：这个题和131.分割回文串一样都是对字符串进行分割，只不过这个子字符串判断时是看是不是0-225之间的数字。
回溯三部曲：
1、递归函数参数：全局变量：String数组result存放结果集。 递归函数参数：原字符串；startIndex，因为切割过的地方不能重复切割，和组合问题是一样的；变量pointNum，记录添加逗点的数量。
2、终止条件：终止条件和131.分割回文串 (opens new window)不同，本题明确要求只会分成4段，所以不能用切割线切到最后作为终止条件，而是分割的段数作为终止条件。pointNum表示逗点数量，pointNum为3说明字符串分成了4段了。
3、单层搜索的逻辑：在for (int i = startIndex; i < s.size(); i++)循环中，我们定义了起始位置startIndex，那么 [startIndex, i] 就是要截取的子串。首先判断这个子串是不是在0-225之间且首位不为0，如果是，就加入path中，path用来记录切割过的回文子串。
代码如下：
class Solution {
List<String> result=new ArrayList<>();
public List<String> restoreIpAddresses(String s) {
StringBuilder sb=new StringBuilder(s);
backTracking(sb,0,0);
return result;
}
public void backTracking(StringBuilder sb,int startIndex,int pointNum){
if(pointNum==3){
if(isValid(sb,startIndex,sb.length()-1)){
result.add(sb.toString());
}
return;
}
for(int i=startIndex;i<sb.length();i++){
if(isValid(sb,startIndex,i)){
sb.insert(i+1,'.');
backTracking(sb,i+2,pointNum+1);
sb.deleteCharAt(i+1);
}else break;
}
}
public boolean isValid(StringBuilder sb,int start,int end){
if(start>end) return false;
if(sb.charAt(start)=='0' && start<end) return false;
int num=0;
for(int i=start;i<=end;i++){
int digit=sb.charAt(i)-'0';
num=num*10+digit;
if(num>255) return false;
}
return true;
}
}
78.子集
思路：感觉和组合问题差不多，关键问题在于如何确定递归的深度。一个很清晰的思路：组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点，所以在遍历树时将所有节点进行记录即可。
回溯三部曲：
1、递归函数参数：全局变量：数组result存放结果集，path存放遍历到的每个节点。 递归函数参数：原数组；startIndex，和组合问题一样无序不能重复。
2、终止条件：startIndex遍历完数组，大于等于数组的长度；可以不需要加终止条件，因为startIndex >= nums.length，本层for循环本来也结束了。
3、单层搜索的逻辑：在for (int i = startIndex; i < s.size(); i++)循环中，我们定义了起始位置startIndex，那么 [startIndex, i] 就是要截取的子串。首先判断这个子串是不是在0-225之间且首位不为0，如果是，就加入path中，path用来记录切割过的回文子串。
代码如下：
class Solution {
List<List<Integer>> result=new ArrayList<>();
List<Integer> path=new LinkedList<>();
public List<List<Integer>> subsets(int[] nums) {
backTracking(nums,0);
return result;
}
public void backTracking(int[] nums, int startIndex){
result.add(new ArrayList(path));
for(int i=startIndex;i<nums.length;i++){
path.add(nums[i]);
backTracking(nums,i+1);
path.removeLast();
}
}
}
90.子集II
思路：这个题和40.组合总和II思路类似，即原始数组中存在重复元素，这个时候为了保证最终结果不重复，即同一层内不能有重复的元素。
对数组排序，在循环中加一个条件，如果该元素与前一个元素相同，则continue。
代码如下：
class Solution {
List<List<Integer>> result=new ArrayList<>();
List<Integer> path=new LinkedList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
backTracking(nums,0);
return result;
}
public void backTracking(int[] nums,int startIndex){
result.add(new ArrayList(path));
for(int i=startIndex;i<nums.length;i++){
if(i>startIndex && nums[i]==nums[i-1]) continue;
path.add(nums[i]);
backTracking(nums,i+1);
path.removeLast();
}
}
}