今日学习

复原IP地址

题目链接/文章讲解：https://programmercarl.com/0093.%E5%A4%8D%E5%8E%9FIP%E5%9C%B0%E5%9D%80.html

视频讲解：https://www.bilibili.com/video/BV1XP4y1U73i/

第一想法

根据分割字符串的方法，首先要判断提取slice出的数是否合法，然后push.join('.'）之后回溯的算法和分割字符串类似

/**
 * @param {string} s
 * @return {string[]}
 */
let res = []
let path = []
var restoreIpAddresses = function (s) {
    res = []
    path = []
    backtracking(s,0)
    return res
};
const youxiao = function (s) {
    if (s.length > 3 || parseInt(s) > 255) return false
    else if (s.length > 1 && s[0] === '0') return false
    else return true
}
const backtracking = function (s, startindex) {
    if(path.length > 4) return
    if (path.length ===4 && startindex >= s.length) {
        res.push(path.join('.'))
        return
    }

    for (let i = startindex; i < s.length; i++) {
        let str = s.slice(startindex, i + 1)
        if (!youxiao(str)) break
        path.push(str)
        backtracking(s, i + 1)
        path.pop()
    }
}

子集

题目链接/文章讲解：https://programmercarl.com/0078.%E5%AD%90%E9%9B%86.html

视频讲解：https://www.bilibili.com/video/BV1U84y1q7Ci

第一想法

该回溯不需要返回，只需要res.push就可以，比较简单

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
let path = []
let res = [[]]
var subsets = function (nums) {
    path = []
    res = []
    backtracking(nums, 0)
    return res
};

const backtracking = function (nums, startindex) {
    if (true) {
        res.push([...path])
    }

    for (let i = startindex; i < nums.length; i++) {
        path.push(nums[i])
        backtracking(nums,i+1)
        path.pop()
    }
}

90.子集II

题目链接/文章讲解：https://programmercarl.com/0090.%E5%AD%90%E9%9B%86II.html

视频讲解：https://www.bilibili.com/video/BV1vm4y1F71J

第一想法

加入一个去重，其他和上一题一样

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
let path = []
let res = []
var subsetsWithDup = function (nums) {
    path = []
    res = []
    nums.sort()
    backtracking(nums, 0)
    return res
};

const backtracking = function (nums, startindex) {
    if (true) {
        res.push([...path])
    }

    for (let i = startindex; i < nums.length; i++) {
        if (i > startindex && nums[i] === nums[i - 1]) continue
        path.push(nums[i])
        backtracking(nums, i + 1)
        path.pop()
    }
}