回溯章节理论基础：
https://programmercarl.com/%E5%9B%9E%E6%BA%AF%E7%AE%97%E6%B3%95%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html
93.复原IP地址
题目链接：https://leetcode.cn/problems/restore-ip-addresses/
思路：
这是切割问题，切割问题就可以使用回溯搜索法把所有可能性搜出来，和刚做过的131.分割回文串 就十分类似了。
startIndex一定是需要的，因为不能重复分割，记录下一层递归分割的起始位置。
本题我们还需要一个变量pointNum，记录添加分割点的数量。
终止条件和131.分割回文串 (opens new window)情况就不同了，本题明确要求只会分成4段，所以不能用切割线切到最后作为终止条件，而是分割的段数作为终止条件。
count代表分割点的数量，为3就说明分成4段了。然后验证一下第四段是否合法，如果合法就加入到结果集里。
class Solution {
List<String> result = new ArrayList<>();
String s;
public List<String> restoreIpAddresses(String s) {
StringBuilder sb = new StringBuilder(s);
backtracking(sb,0,0);
return result;
}
// num代表添加分割点的数量
public void backtracking(StringBuilder s, int startIndex, int count){
// 终止条件
if(count == 3)
{
if(isValid(s,startIndex,s.length()-1))
result.add(s.toString());
return ;
}
for(int i= startIndex ; i<s.length() ; i++){
if(isValid(s,startIndex,i))
{
s.insert(i+1, '.');
// 还多了一个.
backtracking(s,i+2,count+1);
s.deleteCharAt(i+1);
}else
break;
}
}
public boolean isValid(StringBuilder s, int startIndex, int endIndex){
if(startIndex > endIndex || endIndex - startIndex > 2)
return false;
// 把第一个字符是0的情况排除掉 “023”
if(s.charAt(startIndex) == '0' && startIndex != endIndex)
return false;
// 这里不能用int直接转，有可能会超出上界
// if(Integer.parseInt(s.toString().substring(startIndex,endIndex+1))<=255)
// return true;
int num = 0;
for(int i= startIndex;i <= endIndex ; i++){
char tmp = s.charAt(i);
// 遇到非数字字符不合法
if(tmp > '9' || tmp <'0')
return false;
num = num * 10 + tmp - '0';
if(num > 255)
return false;
}
return true;
}
}
78.子集
题目链接：https://leetcode.cn/problems/subsets/
思路：
求子集问题和77.组合 (opens new window)和131.分割回文串 (opens new window)又不一样了。
如果把 子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点。
剩余集合为空的时候，就是叶子节点。
当startIndex已经大于数组的长度了，就终止了，因为没有元素可取了，其实可以不需要加终止条件，因为startIndex >= nums.size()，本层for循环本来也结束了。
同时，求取子集问题，不需要任何剪枝！因为子集就是要遍历整棵树。
class Solution {
List<List<Integer>> result = new ArrayList<>();
List<Integer> paths = new ArrayList<>();
// 这道题和之前的不同之处，不是在叶子结点收获结果了，而是在每一层递归都要进行收获单个结果
public List<List<Integer>> subsets(int[] nums) {
// 默认情况
// result.add(new ArrayList<>(paths));
backtracking(nums , 0);
return result;
}
public void backtracking(int[] nums, int startIndex){
result.add(new ArrayList<>(paths));
if(startIndex >= nums.length) return ;
for(int i= startIndex;i<nums.length;i++){
paths.add(nums[i]);
backtracking(nums, i+1);
// 回溯，比如当遍历到1,2的位置。需要把2回溯，然后才能遍历到1,3
paths.removeLast();
}
}
}
时间复杂度: O(n * 2^n)
空间复杂度: O(n)
90.子集II
题目链接：https://leetcode.cn/problems/subsets-ii/
思路：
这道题目和78.子集 (opens new window)区别就是集合里有重复元素了，而且求取的子集要去重。
那么关于回溯算法中的去重问题，在40.组合总和II 中已经详细讲解过了，和本题是一个套路。
这里要理解“树层去重”和“树枝去重”！从图中可以看出，同一树层上重复取2 就要过滤掉，同一树枝上就可以重复取2，因为同一树枝上元素的集合才是唯一子集！
class Solution {
List<List<Integer>> result = new ArrayList<>();
List<Integer> paths = new ArrayList<>();
boolean[] used;
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
used = new boolean[nums.length];
Arrays.fill(used,false);
// 加入空集，预处理
// result.add(new ArrayList<>(paths));
backtracking(nums,0);
return result;
}
public void backtracking(int[] nums, int startIndex){
result.add(new ArrayList<>(paths));
// if(startIndex >= nums.length) return ;
for(int i = startIndex; i < nums.length ;i++){
if(i>0 && nums[i] == nums[i-1] && used[i-1] == false){
continue ;
}
paths.add(nums[i]);
used[i] = true;
backtracking(nums,i+1);
paths.removeLast();
used[i] = false;
}
}
}
时间复杂度: O(n * 2^n)
空间复杂度: O(n)
