算法训练（leetcode）二刷第二十天 | 93. 复原 IP 地址、78. 子集、90. 子集 II

93. 复原 IP 地址

leetcode题目地址

本题和131. 分割回文串思路相似，回溯法进行数字拼接，判断当前数字是否符合要求，若符合则递归寻找下一个字段，若不符合则继续向后拼接。

时间复杂度： $O(3^4)$
空间复杂度： $O(n)$

// java
class Solution {private int curCnt = 0;private List<String> path = new LinkedList<>();private List<String> result = new ArrayList<>();public boolean isValid(StringBuilder sb){// 前导0if(sb.length() > 1 && sb.charAt(0)=='0') return false;int sum=0;for(int i=0; i<sb.length(); i++){sum = sum*10 + sb.charAt(i) - '0';}// 0-255if(sum>=0 && sum<=255) return true;return false;}public void backtracking(String s, int startIdx){if(path.size() == 4 && startIdx >= s.length()){ // StringBuilder res = new StringBuilder();for(String num : path){res.append(num).append('.');}res.deleteCharAt(res.length()-1);result.add(res.toString());return;}StringBuilder sb = new StringBuilder();for(int i=startIdx; i<s.length(); i++){sb.append(s.charAt(i));if(isValid(sb)){path.add(sb.toString());backtracking(s, i+1);path.removeLast();}}}public List<String> restoreIpAddresses(String s) {if(s.length() > 12) return this.result;backtracking(s, 0);return this.result;}
}

78. 子集

leetcode题目地址

经典回溯问题，只是每一步都要放入结果集。

时间复杂度： $O(n\ast 2^n)$
空间复杂度： $O(n)$

// java
class Solution {public List<Integer> path = new LinkedList<>();public List<List<Integer>> result = new ArrayList<>();public void backtracking(int[] nums, int startIdx){result.add(new ArrayList<>(path));if(startIdx >= nums.length){return;}for(int i=startIdx; i<nums.length; i++){path.add(nums[i]);backtracking(nums, i+1);path.removeLast();}}public List<List<Integer>> subsets(int[] nums) {backtracking(nums, 0);return result;}
}

90. 子集 II

leetcode题目地址

本题和上题的思路相似，只是多了一个去重的步骤。题目要求不能包含重复的子集，也就是在当前层若有相同元素已经查找过了，则跳过当前元素。需要先对数组排序，这样相同元素就连在一起，每层只查找相同元素中的第一个元素，其他相同元素跳过。

时间复杂度： $O(n\ast 2^n)$
空间复杂度： $O(n)$

// java
class Solution {private List<Integer> path = new LinkedList<>();private List<List<Integer>> result = new ArrayList<>();public void backtracking(int[] nums, int startIdx){result.add(new ArrayList<>(path));if(startIdx >= nums.length) {return;}for(int i=startIdx; i<nums.length; i++){// 去重if(i != startIdx && nums[i] == nums[i-1]) continue;path.add(nums[i]);backtracking(nums, i+1);path.removeLast();}}public List<List<Integer>> subsetsWithDup(int[] nums) {Arrays.sort(nums);backtracking(nums, 0);return result;}
}