93.复原IP地址
本期本来是很有难度的，不过 大家做完 分割回文串 之后，本题就容易很多了
题目链接/文章讲解：https://programmercarl.com/0093.复原IP地址.html
视频讲解：https://www.bilibili.com/video/BV1XP4y1U73i/
和分割字符串类似，还有判断当前数字是否符合要求
function isValid(str, start, end) {
if (end - start === 0) {
let num = Number(str[start]);
if (num<0) {
return false;
}
return true;
} else {
if (str[start] === '0') return false;
let num = Number(str.slice(start, end+1));
if (num>255) {
return false;
}
return true;
}
}
/**
* @param {string} s
* @return {string[]}
*/
var restoreIpAddresses = function(s) {
const res = [];
const path = [];
const backtraversing = (str, startIndex) => {
if (path.length>4) return;
if (path.length === 4) {
if (startIndex >= str.length) {
res.push(path.join('.'))
}
return;
}
let len = startIndex+3 > str.length ? str.length : startIndex+3;
for (let i=startIndex; i<len; i++) {
if (isValid(str, startIndex, i)) {
path.push(str.slice(startIndex, i+1));
backtraversing(str, i+1);
path.pop();
} else {
continue;
}
}
}
backtraversing(s, 0);
return res;
};
78.子集
子集问题，就是收集树形结构中，每一个节点的结果。 整体代码其实和 回溯模板都是差不多的。
题目链接/文章讲解：https://programmercarl.com/0078.子集.html
视频讲解：https://www.bilibili.com/video/BV1U84y1q7Ci
/**
* @param {number[]} nums
* @return {number[][]}
*/
var subsets = function(nums) {
const res = [];
const path = [];
const backtraversing = (nums, startIndex) => {
if (startIndex<=nums.length) {
res.push([...path]);
}
for (let i=startIndex; i<nums.length; i++) {
path.push(nums[i]);
backtraversing(nums, i+1);
path.pop();
}
}
backtraversing(nums, 0);
return res;
};
90.子集II
大家之前做了 40.组合总和II 和 78.子集 ，本题就是这两道题目的结合，建议自己独立做一做，本题涉及的知识，之前都讲过，没有新内容。
题目链接/文章讲解：https://programmercarl.com/0090.子集II.html
视频讲解：https://www.bilibili.com/video/BV1vm4y1F71J
/**
* @param {number[]} nums
* @return {number[][]}
*/
var subsetsWithDup = function(nums) {
nums.sort((a,b)=>a-b)
const res = [];
const path = [];
const backtraversing = (nums, startIndex) => {
res.push([...path]);
for (let i=startIndex; i< nums.length; i++) {
if (i>startIndex && nums[i] === nums[i-1]) {
continue;
}
path.push(nums[i]);
backtraversing(nums, i+1);
path.pop();
}
}
backtraversing(nums, 0);
return res;
};