day 28|回溯算法 part04

93.复原IP地址

1. 搞清楚ip地址的有效性：

超过一位的不能以0开头

近一位可以是0

不能超过255（最多三位）

2. 复习： startIndex 相当于就是切割问题的切割点，可以用回溯法全部搜出来

3. Java用StringBuilder来处理字符串，效率会更高 （本题可以把ip地址的每个部分存入一个list）

4.需要考虑到四个ip段，有四个之后就需要结束回溯

这样写更好（工程习惯）

         if(path.size()==4){
             if(startIndex==s.length()){
                 res.add(String.join(".",path));
             }
             return;
         }

如果为4，可以直接结束，进行剪枝，如果为4个ip段时还回溯搜索完了整个字符串，说明可以把当前path加入结果。

78.子集

组合问题且数组中的元素都惟一

子集问题就是找到树的所有节点

画树形结构可知：这种情况利用startIndex 传入i+1来控制子集的可选项。最后遍历所有节点，就相当于记录下了所有的子集集合（不需要剪枝）

保存结果的条件要放在逻辑最开头 （相当于是多叉树的前序遍历位置）空集也相当于遍历到了（多叉树根节点）

可以不写终止条件：1.因为所有节点都要遍历2.startIndex是不断在增大的，会不满足for循环条件，相当于直接return，所以不会进入死循环；

如果要写终止条件，收获结果应该要写在终止条件前面，否则会漏掉自己

class Solution {
    List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合
    LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果
    public List<List<Integer>> subsets(int[] nums) {
        subsetsHelper(nums, 0);
        return result;
    }

    private void subsetsHelper(int[] nums, int startIndex){
        result.add(new ArrayList<>(path));//「遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合」。
        if (startIndex >= nums.length){ //终止条件可不加
            return;
        }
        for (int i = startIndex; i < nums.length; i++){
            path.add(nums[i]);
            subsetsHelper(nums, i + 1);
            path.removeLast();
        }
    }
}

90.子集II

与上题区别：要处理重复项：

重复项要点复习：

树枝去重与树层去重

去重题一定要对集合排序