第一题：93.复原IP地址
-
整体思路：
本题要求根据给定的只包含数字的字符串s找出所有可能的有效 IP 地址组合，采用回溯算法来解决比较合适。因为需要尝试在字符串的不同位置插入.来分割出四个部分，看是否能构成有效的 IP 地址，回溯算法可以方便地进行这种试探性的组合构造并在不符合条件时回退重新选择。 -
函数功能分析：
restoreIpAddresses函数：这是对外的接口函数，首先判断输入字符串s的长度，如果长度大于 12（因为每个部分最大是 255，四个部分最长就是 12 位数字）直接返回空结果列表result，然后调用backTracking函数开始回溯过程，最后返回结果列表result，里面存储了所有找到的有效 IP 地址字符串。backTracking函数：这是核心的回溯函数，参数startIndex表示当前开始分割字符串的起始位置，pointNum表示已经插入的.的数量。当pointNum等于 3 时，意味着已经插入了 3 个.，此时剩下的字符串部分需要检查是否是一个有效的最后一段 IP 地址数字（通过调用isValid函数判断），如果是则把当前构造好的包含.的字符串加入到结果列表result中并返回。在for循环中，从startIndex开始遍历字符串，对于每个位置i，先判断从startIndex到i这一段字符串是否是有效的 IP 地址段（通过isValid函数判断），如果是有效的，就先在这个位置插入.，然后更新pointNum并继续递归调用backTracking深入下一层去插入下一个.，等这一层递归结束后（不管有没有找到有效组合），需要把插入的.去掉（通过字符串截取操作还原之前的状态），同时pointNum减 1，进行回溯，继续尝试下一个位置插入.，如果当前段不是有效的就直接跳出循环不再往后尝试这个位置之后的分割了。isValid函数：用于判断给定的字符串从start位置到end位置这一段是否是有效的 IP 地址中的一个数字段。首先判断起始和结束位置是否合法，如果起始位置大于结束位置就返回false。接着判断如果首字符是0但不是单独一个0（也就是长度大于 1）也返回false。然后遍历这段字符串，把字符转成数字累加到num中，过程中如果遇到非数字字符就返回false，并且如果最终得到的数字num大于 255 也返回false，如果上述情况都没出现则返回true，说明这一段是有效的 IP 地址数字段。
代码
class Solution {List<String> result = new ArrayList<>();public List<String> restoreIpAddresses(String s) {if(s.length() > 12) return result;backTracking(s,0,0);return result;}private void backTracking(String s,int startIndex,int pointNum){if(pointNum == 3){if( isValid(s,startIndex,s.length() - 1) ){result.add(s);}return;}for(int i = startIndex; i < s.length(); i++){if( isValid(s,startIndex,i) ){s = s.substring(0,i + 1) + "." + s.substring(i + 1);pointNum++;backTracking(s,i + 2,pointNum);pointNum--;s = s.substring(0,i + 1) + s.substring(i + 2);}else{break;}}}private boolean isValid(String s,int start,int end){if(start > end){return false;}if(s.charAt(start) == '0' && start != end){return false;}int num = 0;for(int i = start; i <= end;i++){if(s.charAt(i) > '9' || s.charAt(i) < '0'){return false;}num = num * 10 + (s.charAt(i) - '0');if(num > 255){return false;}}return true;}
}第二题：78.子集
解题思路分析
-
整体思路：
本题要求找出给定整数数组nums的所有子集（幂集），且不能包含重复子集，采用回溯算法来解决是比较合适的思路。可以将其想象成构建一棵多叉树的过程，树的每一层代表从数组中选取元素的不同阶段，每个节点的分支就是选择当前元素或者不选择当前元素，通过遍历这棵树的所有节点路径就能得到所有的子集。 -
函数功能分析：
subsets函数：这是对外的接口函数，它接收整数数组nums作为参数，然后调用subsetsHelper函数开始进行回溯求子集的过程，最后返回存放所有子集的结果列表result。subsetsHelper函数：这是核心的回溯函数，参数startIndex表示在数组nums中当前开始考虑选取元素的起始下标。首先，把当前的path（也就是当前已经选取的元素组成的列表）复制一份添加到result列表中，因为每一个节点对应的状态都是一个子集情况。然后判断startIndex是否大于等于数组nums的长度，如果是就表示已经遍历完数组了，直接返回结束函数（其实这个终止条件在本题中不写也可以，因为for循环的结束条件自然也能保证不会越界，这里写上是一种更清晰的结束逻辑体现）。接着通过for循环，从startIndex开始遍历数组剩下的元素，对于每个位置i，先把nums[i]加入到path中（表示选择了这个元素），然后递归调用subsetsHelper函数，传入i + 1作为新的startIndex去继续考虑下一层的元素选取，等这一层递归结束后（也就是这一个分支探索完了），需要把刚加入的nums[i]从path中移除（通过removeLast操作，因为path是用LinkedList实现，方便从末尾移除元素），这样就实现了回溯，能继续尝试下一个元素选或者不选的情况，以此来遍历所有可能的子集组合。
代码
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
解题思路分析
-
整体思路：
本题与 “子集” 问题类似，不过输入的数组nums中可能包含重复元素，要求返回不包含重复子集的所有子集情况，整体依然采用回溯算法来解决。关键在于要处理好重复元素，避免生成重复的子集。思路是先对数组进行排序，这样相同的元素会相邻，在回溯构建子集的过程中，通过额外的标记数组used来判断是否已经使用过相同元素的前一个元素，以此来决定是否跳过当前元素，从而避免重复子集的产生。 -
函数功能分析：
subsetsWithDup函数：首先判断输入数组nums的长度，如果长度为 0，直接把当前的path（初始为空）添加到结果列表result中并返回。接着对nums数组进行排序，方便后续处理重复元素，然后初始化标记数组used（用于记录每个元素是否已经在当前路径中被使用过），最后调用subsetsWithDupHelper函数开始回溯求子集的过程，最后返回存放所有子集的结果列表result。subsetsWithDupHelper函数：这是核心的回溯函数，参数startIndex表示在数组nums中当前开始考虑选取元素的起始下标。先把当前的path（也就是当前已经选取的元素组成的列表）复制一份添加到result中，因为每一个节点对应的状态都是一个子集情况。然后判断startIndex是否大于等于数组nums的长度，如果是就表示已经遍历完数组了，直接返回结束函数。接着通过for循环，从startIndex开始遍历数组剩下的元素，对于每个位置i，需要进行一个关键的重复判断：如果i > 0且当前元素nums[i]和前一个元素nums[i - 1]相等，并且前一个元素nums[i - 1]还没有被使用过（!used[i - 1]），那就说明当前元素和前一个重复且前一个还没在当前路径中使用完，按照避免重复子集的规则，需要跳过当前元素（通过continue语句）；如果不满足这个重复判断条件，就把nums[i]加入到path中（表示选择了这个元素），同时将used[i]标记为true表示这个元素已被使用，然后递归调用subsetsWithDupHelper函数，传入i + 1作为新的startIndex去继续考虑下一层的元素选取，等这一层递归结束后（也就是这一个分支探索完了），需要把刚加入的nums[i]从path中移除（通过removeLast操作），同时把used[i]标记变回false，实现回溯，能继续尝试下一个元素选或者不选的情况，以此来遍历所有可能的子集组合且避免重复子集出现。
代码
class Solution {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();boolean[] used;public List<List<Integer>> subsetsWithDup(int[] nums) {if(nums.length == 0){result.add(path);return result;}Arrays.sort(nums);used = new boolean[nums.length];subsetsWithDupHelper(nums,0);return result;}private void subsetsWithDupHelper(int[] nums,int startIndex){result.add(new ArrayList<>(path));if(startIndex >= nums.length){return ;}for(int i = startIndex;i < nums.length;i++){if(i > 0 && nums[i] == nums[i - 1] && !used[i - 1]){continue;}path.add(nums[i]);used[i] = true;subsetsWithDupHelper(nums,i+1);path.removeLast();used[i] = false;}}
}
