Day 28 | 93.复原 IP 地址、78.子集、90.子集 II

Leetcode 93.复原 IP 地址

题目：93.复原 IP 地址

初始思路

代码

var restoreIpAddresses = function (s) {
    const res = [], path = [];
    backtracking(0, 0)
    return res;
    function backtracking (i) {
        const len = path.length;
        if (len > 4) return;
        if (len === 4 && i === s.length) {
            res.push(path.join("."));
            return;
        }
        for (let j = i; j < s.length; j++) {
            const str = s.slice(i, j + 1);
            if (str.length > 3 || +str > 255) break;
            if (str.length > 1 && str[0] === "0") break;
            path.push(str);
            backtracking(j + 1);
            path.pop()
        }
    }
};

感想

1. 需要判断到底截了几段，还要判断是否有前导0和数字范围。
   

Leetcode 78.子集

题目：78.子集

初始思路

这题原来写过一次，感觉像模板题。

代码

var subsets = function (nums) {
    const res = []
    const path = []
    const backtracking = (startIndex) => {
        // 收集子集，要放在终止添加的上面，否则会漏掉自己
        res.push([...path])
        if (startIndex >= nums.length) return
        for (let i = startIndex; i < nums.length; i++) {
            path.push(nums[i])
            backtracking(i + 1)
            path.pop()
        }
    }
    backtracking(0)
    return res
};

感想

1. 如果把 子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！其实子集也是一种组合问题，因为它的集合是无序的，子集{1,2} 和 子集{2,1}是一样的。那么既然是无序，取过的元素不会重复取，写回溯算法的时候，for就要从startIndex开始，而不是从0开始！
2. 求排列问题的时候，就要从0开始，因为集合是有序的，{1, 2} 和{2, 1}是两个集合。
3. 

Leetcode 90.子集 II

题目：90.子集 II

初始思路

跟上一题不同的是，这题有重复元素，而且不能有重复的子集。在昨天的40题中也进行了去重操作。

代码

var subsetsWithDup = function (nums) {
    let res = []
    let path = []
    nums.sort((a, b) => a - b)
    const backtracking = (startIndex) => {
        // 收集子集，要放在终止添加的上面，否则会漏掉自己
        res.push([...path])
        if (startIndex >= nums.length) return
        for (let i = startIndex; i < nums.length; i++) {
            if (i > startIndex && nums[i] === nums[i - 1]) continue
            path.push(nums[i])
            backtracking(i + 1)
            path.pop()
        }
    }
    backtracking(0)
    return res
};

感想

1. 从图中可以看出，同一树层上重复取2 就要过滤掉，同一树枝上就可以重复取2，因为同一树枝上元素的集合才是唯一子集！