39、组合总和|39、组合总和 | 算法（leetode，附思维导图 + 全部解法）300题 39、组合总和|算法（leetode，附

零标题：算法（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][pre]) { dp[i][j].push(item.concat(new Array(k).fill(candidates[i - 1]))); } } } } }// 3）返回结果 dp 数组 return dp; };

3 方案3
【39、组合总和|39、组合总和 | 算法（leetode，附思维导图 + 全部解法）300题】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]; };