leetcode-回溯（JS实现）

本文主要是介绍leetcode-回溯（JS实现），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

46. 全排列

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    const res = [];
    const used = {};
    function dfs(path) {
        if(path.length === nums.length){
            res.push(path.slice());
            return res;
        }
        for(let i = 0; i < nums.length; i++) {
            if(used[i]) continue
            path.push(nums[i]);
            used[i] = true;
            dfs(path);
            path.pop();
            used[i] = false;
        }
    }
    dfs([]); 
    return res;
};

47. 全排列 II

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function(nums) {
    let res = [];
    let used = {};
    nums.sort((a,b)=>a-b);
    const dfs = (path) => {
        if(path.length === nums.length){
            res.push(path.slice());
            return res;
        }
        for(let i = 0; i < nums.length; i++) {
            if(used[i]) continue
            if(i-1>=0 && nums[i] === nums[i-1] && !used[i-1]) continue;
            path.push(nums[i]);
            used[i] = true;
            dfs(path);
            path.pop();
            used[i] = false;
        }
    }
    dfs([]);
    return res;
};

39. 组合总和

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
    let res = [];
    const dfs = (start, temp, sum) => {
        if(sum >= target){
            if(sum === target){
                res.push(temp.slice());
            }
            return;
        }
        for(let i = start; i < candidates.length; i++){
            temp.push(candidates[i]);
            dfs(i, temp, sum + candidates[i]);
            temp.pop();
        }
    }
    dfs(0,[],0);
    return res;
};

40. 组合总和 II

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function(candidates, target) {
    let res = [];
    candidates.sort((a,b)=>a-b);
    const dfs = (start,temp,sum)=>{
        if(sum>=target){
            if(sum === target){
                res.push(temp.slice());
            }
            return;
        }
        for(let i = start; i < candidates.length; i++){
            if(i-1>=start && candidates[i] === candidates[i-1]){
                continue;
            }
            temp.push(candidates[i]);
            dfs(i+1, temp, sum + candidates[i]);
            temp.pop();
        }
    }
    dfs(0,[],0);
    return res;
};

216. 组合总和 III

/**
 * @param {number} k
 * @param {number} n
 * @return {number[][]}
 */
var combinationSum3 = function(k, n) {
    let res = [];
    const dfs = (start,temp,sum) => {
        if(temp.length === k) {
            if(sum === n) {
                res.push(temp.slice());
            }
            return;
        }
        for(let i = start; i <= 9; i++){
            temp.push(i);
            dfs(i+1,temp,sum + i);
            temp.pop();
        }
    }
    dfs(1,[],0);
    return res;
};

78. 子集

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
    let res=[];
    const dfs = (start, temp) => {
        res.push(temp.slice());
        for(let i = start; i < nums.length; i++){
            temp.push(nums[i]);
            dfs(i+1, temp);
            temp.pop();
        }
    };
    dfs(0,[]);
    return res;
};

90. 子集 II

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsetsWithDup = function(nums) {
    let res=[];
    nums.sort((a,b)=>a-b);
    const dfs = (start,temp) => {
        res.push(temp.slice());
        for(let i = start; i < nums.length; i++){
            if(i-1 >= start && nums[i-1]===nums[i]){
                continue;
            }
            temp.push(nums[i]);
            dfs(i+1,temp);
            temp.pop();
        }
    }
    dfs(0,[]);
    return res;
};

这篇关于leetcode-回溯（JS实现）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！