零 题目：算法（leetode，附思维导图 + 全副解法）300 题之（39）组合总和

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

一 题目形容

二 解法总览（思维导图）

三 全副解法

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]

) {

                        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

 === undefined) dp

 = [];

            if (dp

.length === 0 && pre === 0) {

                dp[j].push([candidates[i]]); // target 刚好等于以后物品 

            } else {

                const t = [];

                for (const item of dp

) {

                    const tt = Array.from(item); // 拷贝 

                    tt.push(candidates[i]);

                    t.push(tt);

                }

                dp[j].push(...t);

            }

        }

    }
    // 3）返回后果 dp[target]

    return dp[target];

};