算法训练（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){
        // 前导0
        if(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-255
        if(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;
    }
}