LeetCode:93.复原IP地址
1.思路
使用逗点分割字符，对每段字符进行范围，内容的有效性进行检验，当逗点数量为3时，字符被分割成四段，以此作为终止条件。for循环横向遍历，backTracking()回溯遍历。其中字符串区间选择是难点。
2.代码实现
1class Solution { 2 List<String> result = new ArrayList<>(); // 存储字符数组的结果集 3 4 public List<String> restoreIpAddresses(String s) { 5 StringBuilder sb = new StringBuilder(s); // 临时字符串 6 backTracking(sb, 0, 0); // 回溯函数 7 return result; // 完成遍历，返回结果集 8 } 9 10 private void backTracking(StringBuilder s, int startIndex, int dotCount) { 11 if (dotCount == 3) { // 逗点数量== 3 时，终止条件 12 if (isValid(s, startIndex, s.length() - 1)) { // 判断是否有效，有效加入结果集，否则进行剪枝操作 13 result.add(s.toString()); 14 } 15 return; 16 } 17 18 // 横向遍历 19 for (int i = startIndex; i < s.length(); i++) { 20 if (isValid(s, startIndex, i)) { // 判断遍历的一段段字符是否有效 21 s.insert(i + 1, '.'); // 有效则加入逗点 22 backTracking(s, i + 2, dotCount + 1); // 调用回溯函数寻找下一段符合条件的字符串 23 s.deleteCharAt(i + 1); // 回溯，删除的是逗点 24 } else { 25 break; // 无效则进行剪枝操作 26 } 27 } 28 } 29 30 // 构建字符有效性的函数 31 private boolean isValid(StringBuilder s, int start, int end) { 32 if (start > end) { // 字符子串为空，则无效，返回false 33 return false; 34 } 35 if (s.charAt(start) == '0' && start != end) { // 含有多个字符且首个字符为0，则无效，返回false 36 return false; 37 } 38 39 int num = 0; 40 for (int i = start; i <= end; i++) { 41 int digit = s.charAt(i) - '0'; // 将字符转换为数字 42 num = num * 10 + digit; // 将数字组合起来 43 if (num > 255) { // 数字大于255，则无效，返回false 44 return false; 45 } 46 } 47 return true; // 字符子串有效，返回true 48 } 49}
3.复杂度分析
时间复杂度：每一段数字最大为3，每次最多递归四次，O(S*3^4).
空间复杂度：临时字符串sb对空间开销 + 递归函数使用栈的开销
LeetCode:78.子集
1.思路
子集问题，直接横向遍历嵌套递归遍历，将所有结果加入结果集即可
2.代码实现
1class Solution { 2 List<List<Integer>> result = new ArrayList<>(); // 存放结果的结果集 3 LinkedList<Integer> path = new LinkedList<>(); // 存放单个结果 4 public List<List<Integer>> subsets(int[] nums) { 5 6 backtracking(nums, 0); // 递归 7 return result; // 返回结果集 8 } 9 private void backtracking(int[] nums, int startIndex) { 10 result.add(new ArrayList<>(path)); // 加入结果集 11 if (startIndex >= nums.length) { // 当遍历到最后阶段时的终止条件 12 return; 13 } 14 // 横向遍历 15 for (int i = startIndex; i < nums.length; i++) { 16 path.add(nums[i]); // 加入到结果集 17 backtracking(nums, i + 1); // 递归加入元素 18 path.removeLast(); // 回溯 删除元素 19 } 20 } 21}
3.复杂度分析
时间复杂度：一次遍历经历一个for循环和一个递归，一个元素要经历n次遍历，则为2^n.而n个元素需要n*2^n.
空间复杂度：取决于栈空间和堆空间的开销，O(n + m)
LeetCode:90.子集II
1.思路
将数组抽象成树形结构，先排序，定义一个used数组进行标记数层去重，for循环横向遍历，backtracking()递归遍历，当位置超过数组长度就是终止条件.
2.代码实现
1class Solution { 2 List<List<Integer>> result = new ArrayList<>(); // 存放符合条件结果的结果集 3 LinkedList<Integer> path = new LinkedList<>(); // 符合条件的结果 4 boolean[] used; // 记录是否被使用的数组，需要和排序结合使用 5 public List<List<Integer>> subsetsWithDup(int[] nums) { 6 if (nums.length == 0) { // 当数组元素为空时，直接返回即可 7 result.add(path); 8 return result; 9 } 10 Arrays.sort(nums); // 数组进行排序 11 used = new boolean[nums.length]; // 初始化used[] 12 subsetsWithDupHelper(nums, 0); // 调用回溯函数 13 return result; // 返回结果集 14 } 15 // 构建回溯函数 16 private void subsetsWithDupHelper(int[] nums, int startIndex) { 17 result.add(new ArrayList<>(path)); // 将符合条件的结果path加入到结果集中 18 if (startIndex >= nums.length) { // 终止条件 19 return; 20 } 21 // 横向遍历 22 for (int i = startIndex; i < nums.length; i++) { 23 // 数层去重 24 if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) { 25 continue; 26 } 27 path.add(nums[i]); // 符合条件的加入结果path中 28 used[i] = true; // 将该标记值改为true 29 subsetsWithDupHelper(nums, i + 1); // 递归调用 30 path.removeLast(); // 回溯 31 used[i] = false; // 置为false 32 } 33 } 34}
3.复杂度分析
时间复杂度：O(n!)
空间复杂度：O(n^2)
