今日学习

递增子序列

https://programmercarl.com/0491.%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97.html

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

第一想法

回溯，然后进行树层去重，【6，7，7】是通过树枝生成的

/**
 * @param {number[]} nums
 * @return {number[][]}
 */

let path = []
let res = []
var findSubsequences = function (nums) {
    path = []
    res = []
    backtracking(nums, 0)
    return res
};

const backtracking = function (nums, startindex) {
    if (path.length >= 2) {
        res.push([...path])
        //不能return
    }
    let uset = new Set()
    for (let i = startindex; i < nums.length; i++) {
        if ((path.length > 0 && nums[i] < path[path.length - 1]) || uset.has(nums[i])) continue

        path.push(nums[i])
        uset.add(nums[i])
        backtracking(nums, i + 1)
        path.pop()
    }
}

全排列

https://programmercarl.com/0046.%E5%85%A8%E6%8E%92%E5%88%97.html

第一想法

排列不需要用到startindex，只需要记录这一层用过的used，传给下一层回溯，然后进行排列

/**
 * @param {number[]} nums
 * @return {number[][]}
 */

let path = []
let res = []
let used = []
var permute = function (nums) {
    path = []
    res = []
    used = []
    backtracking(nums, used)
    return res
};

const backtracking = function (nums, used) {
    if (path.length === nums.length) {
        res.push([...path])
        return
    }

    for (let i = 0; i < nums.length; i++) {
        if (used[i] === true) continue
        path.push(nums[i])
        used[i] = true
        backtracking(nums, used)
        path.pop()
        used[i] = false
    }
}

全排列 II

第一想法

这道题很神奇，树枝数层去重都可以，但我这么写让我更好理解一些

/**
 * @param {number[]} nums
 * @return {number[][]}
 */

let path = []
let res = []
let used = []
var permuteUnique = function (nums) {
    path = []
    res = []
    used = new Array(nums.length).fill(false);
    nums.sort()
    backtracking(nums, used)
    return res

};
const backtracking = function (nums, used) {
    if (nums.length === path.length) {
        res.push([...path])
        return
    }

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