93. 复原 IP 地址

解题思路：

注意isValid函数判断的时候要用字符0来判断。

var restoreIpAddresses = function (s) {
    const res = [];
    const path = [];
    const isValid = (str) => {
        const strNum = Number(str);
        if (str.length !== 1 && str[0] === '0') {
            return false;
        }
        if (strNum < 0 || strNum > 255) {
            return false;
        }
        return true;
    }
    const backtracking = (s, startIndex) => {
        if (path.length === 4 && startIndex === s.length) {
            res.push(path.join("."));
            return;
        }
        for (let i = startIndex; i < s.length; i++) {
            const str = s.slice(startIndex, i + 1);
            if (!isValid(str)) {
                break;
            }
            path.push(str);
            backtracking(s, i + 1);
            path.pop();
        }
    }
    backtracking(s, 0);
    return res;
};

78. 子集

解题思路：

注意收集节点的位置在于树中除了根节点以外的所有节点，所以需要再函数一开始就写。

var subsets = function (nums) {
    const res = [];
    const path = [];
    const backtracking = (nums, startIndex) => {
        res.push(Array.from(path));
        for (let i = startIndex; i < nums.length; i++) {
            path.push(nums[i]);
            backtracking(nums, i + 1);
            path.pop();
        }
    }
    backtracking(nums, 0);
    return res;
};

90. 子集 II

解题思路：

相对于子集这道题，只需要增加一个used数组，注意这里去重的逻辑应该是树层的去重，在树枝上面是可以重复使用的。

var subsetsWithDup = function (nums) {
    const path = [];
    const res = [];
    const backtracking = (nums, startIndex, used) => {
        res.push(Array.from(path));
        for (let i = startIndex; i < nums.length; i++) {
            if (i > 0 && nums[i] === nums[i - 1] && used[i - 1] === false) {
                continue;
            }
            path.push(nums[i]);
            used[i] = true;
            backtracking(nums, i + 1, used);
            used[i] = false;
            path.pop();
        }
    }
    nums.sort((a, b) => a - b);
    backtracking(nums, 0, []);
    return res;
};