零 题目：算法（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
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];};