491.递增子序列
本题和大家刚做过的 90.子集II 非常像，但又很不一样，很容易掉坑里。
https://programmercarl.com/0491.递增子序列.html
视频讲解：https://www.bilibili.com/video/BV1EG4y1h78v
关键点还要在于本层使用过的数字不能再使用
/**
* @param {number[]} nums
* @return {number[][]}
*/
var findSubsequences = function(nums) {
const res = [];
const path = [];
const backtraversing = (nums, startIndex)=>{
if (path.length>=2) {
res.push([...path]);
}
if (startIndex>nums.length) {
return;
}
const set = new Set();
for (let i=startIndex;i<nums.length;i++) {
let flag = !((nums[i] < path[path.length-1]) || set.has(nums[i]));
if (flag) {
set.add(nums[i]);
path.push(nums[i]);
backtraversing(nums, i+1);
path.pop();
}
}
}
backtraversing(nums,0);
return res;
};
46.全排列
本题重点感受一下，排列问题 与 组合问题，组合总和，子集问题的区别。 为什么排列问题不用 startIndex
https://programmercarl.com/0046.全排列.html
视频讲解：https://www.bilibili.com/video/BV19v4y1S79W
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permute = function(nums) {
const res = [];
const path = [];
const used = new Array(nums.length).fill(false);
const backtraversing = (nums) => {
if (path.length === nums.length) {
res.push([...path]);
return;
}
for (let i=0; i< nums.length;i++) {
if (used[i]) {
continue;
}
used[i]=true;
path.push(nums[i]);
backtraversing(nums);
path.pop();
used[i]=false;
}
}
backtraversing(nums);
return res;
};
47.全排列 II
本题 就是我们讲过的 40.组合总和II 去重逻辑 和 46.全排列 的结合，可以先自己做一下，然后重点看一下 文章中 我讲的拓展内容。 used[i - 1] == true 也行，used[i - 1] == false 也行
https://programmercarl.com/0047.全排列II.html
视频讲解：https://www.bilibili.com/video/BV1R84y1i7Tm
本层使用过的下一层不能使用，本层使用过的本层也不能再使用
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permuteUnique = function(nums) {
nums.sort((a,b)=>a-b);
const res = [];
const path = [];
const used = new Array(nums.length).fill(false);
const backtraversing = (nums) => {
if (path.length === nums.length) {
res.push([...path]);
return;
}
for (let i=0; i<nums.length; i++) {
if (i > 0 && nums[i] === nums[i-1] && used[i-1] === false) {
continue;
}
if (used[i] === false) {
used[i] = true;
path.push(nums[i]);
backtraversing(nums);
path.pop();
used[i] = false;
}
}
}
backtraversing(nums);
return res;
};