39、组合总和 | 算法(leetode,附思维导图 + 全部解法)300题

零 标题:算法(leetode,附思维导图 + 全部解法)300题之(39)组合总和

码农三少 ,一个致力于编写极简、但齐全题解(算法)的博主

一 题目描述

39、组合总和 | 算法(leetode,附思维导图 + 全部解法)300题_第1张图片
39、组合总和 | 算法(leetode,附思维导图 + 全部解法)300题_第2张图片

二 解法总览(思维导图)

39、组合总和 | 算法(leetode,附思维导图 + 全部解法)300题_第3张图片

三 全部解法

1 方案1

1)代码:

// 方案1 “回溯(本质:递归)法”
// 技巧:说白了,就是通过回溯去穷举所有的情况,根据当前情况进行不同的处理。

// 思路:
// 1)状态初始化
// 2)调用 - 回溯
// 3)返回结果 resList 
var combinationSum = function(candidates, target) {
    const dfs = (curIndex, l, curSum, target, curArr, resList) => {
        // 1)递归出口
        if (curSum === target) {
            // 注:需要使用 slice 获取其副本值!
            resList.push(curArr.slice());
            return;
        }
        if (curIndex >= l || curSum > target) {
            return;
        }

        // 2)递归主体(“核心:回溯 = 选 + 不选”)
        // 2.1)选
        curSum += candidates[curIndex];
        curArr.push(candidates[curIndex]);
        dfs(curIndex, l, curSum, target, curArr,resList);

        // 2.2)不选(“边界:可能需要恢复环境!”)
        curSum -= candidates[curIndex];
        curArr.pop();
        dfs(curIndex + 1, l, curSum, target, curArr, resList);
    };

    // 1)状态初始化
    const l = candidates.length;
    let curIndex = 0,
        curSum = 0,
        curArr = [],
        resList = [];

    // 2)调用 - 回溯
    dfs(curIndex, l, curSum, target, curArr, resList);

    // 3)返回结果 resList 
    return resList;
};

2 方案2

1)代码:

// 方案2 “动态规划 - 普通版”。
// TODO,注:通过 0 / 170,应该是代码哪里写错了!!!

// 思路:
// 1)状态定义:
// dp[i][j] 前i个物品(使用哨兵从1开始)能组合成j的序列

// 2)初始化:
// dp[0][j] = [], 没有物品则没有能组合成j的序列

// 3)转移方程:
// dp[i][j] 的值由两个方向递推得来:
// 当前能选的物品中,不选第i个物品就能组合成目标j的序列,即dp[i - 1][j]
// 当前能选的物品中,选k个第i个物品,即dp[i - 1][j - k * nums[i]]
// 注:动态规划数组中存储的是引用,所以要深拷贝

// 参考:
// 1)https://leetcode-cn.com/problems/combination-sum/solution/dong-tai-gui-hua-bei-bao-wen-ti-by-sjtxw-11yv/
var combinationSum = function(candidates, target) {
    // 1)dp 状态初始化
    const l = candidates.length;
    const dp = new Array(l + 1);
    for (let i = 0; i <= l; i++) {
        dp[i] = new Array(target + 1);
    };
    for (let i = 0; i <= target; i++) {
        dp[0][i] = [];
    };

    // 2)dp 状态转移 并 处理结果
    for (let i = 1; i <= l; i++) {
        dp[i][0] = [];
        for (let j = 1; j <= target; j++) {
            dp[i][j] = [];
            for (const item of dp[i - 1][j]) dp[i][j].push(Array.from(item)); // 不选当前元素
            for (let k = 1; j - k * candidates[i - 1] >= 0; k++) { // 选择k个当前元素
                const pre = j - k * candidates[i - 1];
                if (pre === 0) {
                    dp[i][j].push(new Array(k).fill(candidates[i - 1])); // 刚好k个当前元素
                } else {
                    for (const item of dp[i - 1][pre]) {
                        dp[i][j].push(item.concat(new Array(k).fill(candidates[i - 1])));
                    }
                }
            }
        }
    }

    // 3)返回结果 dp 数组
    return dp;
};

3 方案3

1)代码:

// 方案3 “动态规划 - 优化版”。
// 本质:二维存储空间 压缩成 一维存储空间 

// 思路:
// 1)dp 状态初始化
// 2)dp 状态转移 并 处理结果
// 3)返回结果 dp[target] 
var combinationSum = function(candidates, target) {
    // 1)dp 状态初始化
    const l = candidates.length;
    const dp = new Array(target + 1);
    dp[0] = [];

    // 2)dp 状态转移 并 处理结果
    for (let i = 0; i < l; i++) {
        for (let j = 1; j <= target; j++) {
            if (dp[j] === undefined) dp[j] = [];
            const pre = j - candidates[i];
            if (pre < 0) continue;
            if (dp[pre] === undefined) dp[pre] = [];
            if (dp[pre].length === 0 && pre === 0) {
                dp[j].push([candidates[i]]); // target刚好等于当前物品
            } else {
                const t = [];
                for (const item of dp[pre]) {
                    const tt = Array.from(item); // 拷贝
                    tt.push(candidates[i]);
                    t.push(tt);
                }
                dp[j].push(...t);
            }
        }
    }

    // 3)返回结果 dp[target] 
    return dp[target];
};

你可能感兴趣的